perm filename KNOWL[DIS,DBL]4 blob
sn#220566 filedate 1976-06-14 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00026 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 .NSECP(AM's Knowledge)
C00006 00003 .SSEC(Motivation and Overview)
C00009 00004 . SSSEC(A Glimpse of a Typical Concept)
C00016 00005 . SSSEC(The main constraint: Fixed set of facets)
C00026 00006 . SSSEC(BEINGs Representation of Knowledge)
C00027 00007 .SSEC(Facets)
C00033 00008 . SSSEC(Generalizations/Specializations)
C00043 00009 . SSSEC(Examples/Isa's)
C00056 00010 . SSSEC(In-Domain-of/In-Range-of)
C00071 00011 . SSSEC(Views)
C00081 00012 . SSSEC(Intuitions)
C00090 00013 . SSSEC(Analogies)
C00100 00014 . SSSEC(Conjec's)
C00116 00015 . SSSEC(Definitions)
C00132 00016 . SSSEC(Algorithms)
C00150 00017 . SSSEC(Domain/Range)
C00163 00018 . SSSEC(Worth)
C00171 00019 . SSSEC(Interest)
C00184 00020 . SSSEC(Suggest)
C00191 00021 . SSSEC(Fillin/Check)
C00201 00022 . SSSEC(Other Facets which were Considered)
C00208 00023 .SSEC(AM's Starting Knowledge)
C00209 00024 . SSSEC(Diagram of Initial Concepts)
C00214 00025 . SSSEC(Summary of Initial Concepts)
C00231 00026 . SSSEC(Rationale behind Choice of Concepts)
C00239 ENDMK
C⊗;
.NSECP(AM's Knowledge)
.BEGIN TURN ON "{}"
This chapter contains material about AM's anatomy.
After a brief overview, we'll look in detail at the way concepts are
represented (Section {SECNUM}.2). This includes a discussion of each
kind of facet a concept may possess. Wedged in among the
implementation details and formats are a horde of tiny ideas; they
should be useful to anyone contemplating working on a system similar
in design to AM.
The chapter closes by sketching all the knowledge
AM starts with.
The concepts will be diagrammed, and will also have a brief description,
sufficient for the
reader to follow later chapters without trouble.
Instead of using up a large number of
pages for an unreadable listing of all of the specific information initially
supplied with each concept, such complete coverage is relegated to Appendix
{[2] ALLCON}.$$
That appendix lists each concept alphabetically, giving a condensed
listing of the facts initially given (by the author) to AM about each facet of
that concept. This material is
translated from LISP into English and standard math notation.
Some unmodified "concepts" -- still in LISP -- are displayed in
Appendix {[2] CONS}.
Appendix {[2] EXAM2} gives several examples illustrating
the changes in AM's state of knowledge at
various moments. $
The next chapter starts on page {[3]R1PAGE}.$$Though devoid of theoretical
significance, that sentence has alas proved of high empirical value. $
.END
.SSEC(Motivation and Overview)
Each concept consists merely of a bundle of facets. The facets
represent the different aspects of each concept, the kinds of
questions one might want to ask about the concept:
.B48
How valuable is this concept?
What is its definition?
If it's an operation, what is legally in its domain?
What are some generalizations of this concept?
How can you separate the interesting instances of this concept from
the dull ones?
.E
Since each concept is a mathematical entity, the kinds of questions
one might ask are fairly constant from concept to concept. This set
of questions might change significantly for a new domain of concept
-- say, those dealing with politics$$ On second thought, most of the above
questions would still make sense for political concepts.
Accurate ↓_answers_↓ would be much harder to provide, however:
the algorithm for campaigning is not in the same league as the algorithm
for set-union. $.
One "natural" representation for a concept in LISP is therefore as a
set of attribute/value pairs. That is, each concept is maintained as
an atom with a property list. The names of the properties (Worth,
Definitions, Domain/Range, Generalizations, Interestingness,...)
correspond to the questions above, and the value stored under
property F of atom C is simply the value of the F-facet of the C-concept.
This value can also be viewed as the answer which expert C would give, if asked
question F. Or, it can be viewed as the
contents of slot F of frame C.
. SSSEC(A Glimpse of a Typical Concept)
As an example, here is a stylized rendition of the SETS concept. This
is a concept which is meant to correspond to the notion of a set of
elements. The format P: v↓1,v↓2,... is used to indicate that the value
of property P is the list v↓1,v↓2,... That is, the concept Sets has
entries v↓1,v↓2,... for its facet P. For example,
according to the box below,
"Singleton" is one
entry on the Specializations facet of Sets.
I shall not digress here to explain each of these entries -- and what
are apparently omissions. Such things will be done later in this
chapter$$ The individual facets will be discussed one at a time. This particular
concept will be presented and discussed in detail in Appendix {[2] ALLCON}, on
page... $. For now, just glance at it to get the flavor of what a
concept is like.
.WBOX(10,11)
MBOX Name(s): Set, Class, Collection $
MBOX Definitions: $
MBOX Recursive: λ (S) [S=α{α} or Set.Definition (Remove(Any-member(S),S))] $
MBOX Recursive quick: λ (S) [S=α{α} or Set.Definition (CDR(S))] $
MBOX Quick: λ (S) [Match S with α{...α} ] $
MBOX Specializations: Empty-set, Nonempty-set, Set-of-structures, Singleton $
MBOX Generalizations: Unordered-Structure, No-multiple-elements-Structure $
MBOX Examples: $
MBOX Typical: {{}}, {A}, {A,B}, {3} $
MBOX Barely: {}, {A, B, {C, { { { A, C, (3,3,3,9), <4,1,A,{B},A>}}}}} $
MBOX Not-quite: {A,A}, (), {B,A} $
MBOX Foible: <4,1,A,1> $
MBOX Conjec's: All unordered-structures are sets. $
MBOX Intu's: $
MBOX Geometric: Venn diagram $
MBOX Analogs: bag, list, oset $
MBOX Worth: 600 $
MBOX View: $
MBOX Predicate: λ (P) {xεDomain(P) | P(x)} $
MBOX Structure: λ (S) Enclose-in-braces(Sort(Remove-multiple-elements(S))) $
MBOX Suggest: If P is an interesting predicate over X, consider {xεX | P(x)}. $
MBOX In-domain-of: Union, Intersection, Set-difference, Set-equality, Subset, Member $
MBOX In-range-of: Union, Intersection, Set-difference, Satisfying $
.EBOX
To decipher the Definitions facet, there are a few things you must know.
An expression of the form "(λ (x) E)" is called a Lambda expression
after Church$$
Before and during Church, it's called a function. See [Church]. $,
and may be considered an executable procedure.
it accepts one argument, binds the variable "x"
to the value of that argument, and then
evaluates "E" (which is probably some expression involving the variable x).
For example, (λ (x) (x+5)) is a function which
adds 5 to any number (if given the argument 3, this lambda expression will return
the value 8).
The second thing you must know is that facet F of concept C will occasionally
be abbreviated as C.F. In those cases where F is "executable", the notation
C.F will refer to applying the corresponding function.
So the first entry in the Definitions facet is recursive because it contains
an embedded call on the function Set.Definition.
Notice that we are implying that the ⊗4name⊗*
of that lambda expression itself is "Set.Definition".
There are some bizarre implications of this: since there are three separate but
equivalent definitions, we may choose whichever one we want when we recurse!
AM can choose one via a random selection scheme, or always try to recurse into the
same definition as it was just in, or perhaps suit its choice to the form of
the argument at the moment.
.ONCE TURN ON "{}"
For example, one definition might be great for arguments
of size 10 or less, but slow for bigger ones, and another definition might be
mediocre for all size arguments; then one should
use the mediocre definition over and over again, until the
argument becomes small enough,
and from then on recurse only into the fast definition.
Although AM embodies this "smart" scheme, the little comments necessary to
see how it does so have be excised from the version shown above in the box.
This will be explained later in this chapter, on page {[3] RECURPAGE}.
All concepts possess executable definitions, though not necessarily effective
ones. They each have a LISP predicate, but that predicate is not guaranteed
to terminate. Notice that the definitions for Sets are all definitions of
finite sets.$$ The third definition, "α{...α}", may not look finite, but
consider that ellipsis notation is not permitted within any specific set.$
. SSSEC(The main constraint: Fixed set of facets)
One important constraint on the representation is that the set of
facets be fixed once and for all. There is one fixed, universal list
of two dozen types of facets. Any facet of any concept
⊗4must⊗* have one of those standard names. All concepts which have
some examples must store them as entries on a facet called Examples;
they can't call them Instances, or Cases, or G00037's. This
constraint is known as the "⊗6Beings⊗* constraint"$$ See [Lenat].
Historically, each concept module was called a "BEING". $, and has
three important consequences:
.SKIP 1 BN
λλ OUTLINE: First, it provides a nice, distributed, universal
framework on which to display all that is known about a given
concept. For example, when AM creates a new concept like
"Square-root", the user can judge how well AM understands that
concept by examining its property-list (the list of entries for each
facet). Similarly, AM can instantly tell what facets are not yet
filled in for a given concept, and this will in turn suggest new
tasks to perform. In other words, this constraint helps define the
"space" which AM must explore, and makes it obvious what parts of
each concept have and have not yet been investigated.
λλ STRUCTURE: The constraint specifies that there be a ⊗4set⊗* of
facets, not just one. This set was made large enough that all the
efficiency advantages of a "structured" representation are preserved
(unlike totally uniform representations, e.g. pure production systems
with simple memories as data structures, or predicate calculus).
λλ UNIFORMITY: The most important benefit of the ⊗6Beings⊗*
constraint arises when somebody$$ An anthropomorphism, indicating a
request arising in either side of a heuristic rule, or embedded
within an entry on an executable facet, such as Algorithms. $ wants
to get a particular question answered -- especially if the
information pertains to related concepts. The advantage is that
he'll have a very limited repertoire of questions he may ask, hence
there will be no long searching, no misunderstandings. This is the
same advantage that always arises when everyone uses a common
language.
.E
We shall illustrate the last two advantages by using the Sets concept
pictured in the box a couple pages ago. How does AM handle a task of
this form: "⊗6Check examples of Sets⊗*"? AM accesses the examples
facet of the Sets concept, and obtains a bunch of items which are all
probably sets. If any isn't a set, AM would like to make it one, if
that involves nothing difficult. AM locates all the generalizations
of Sets$$ by "rippling" upward from Sets, in the Genl direction$, and
comes up with the list <Sets, Unordered-Structures,
No-multiple-elements-Structures, Structures, Objects, Any-concept,
Anything>. Next, the "Check" facets of each of these is examined, and
all its heuristics are collected. For example, the Check facet of
the No-multiple-elements-Structures concept contains the following
entry: "Eliminate multiple occurrences of each element" (of course
this is present not as an English sentence but rather as a little
LISP function). So even though Sets has no entries for its Check
facet, several little functions will be gathered up by the rippling
process. Each potential set would be subjected to all those checks,
and might be modified or discarded as a result.
There is enough "structure" around to keep the heuristic rules
relevant to this task isolated from very irrelevant ones, and there
is enough "uniformity" to make finding those rules very easy.
The same rippling would be done to find predicates which tell whether
a set is interesting or dull. For example, one entry on the
Interestingness facet of the Structure concept says that a structure
is interesting if all pairs of members satisfy the same rare
predicate P(x,y) [for any such P]. So a set, all pairs of whose
members satisfy "Equality," would be considered interesting. In fact,
every Singleton is an interesting structure for just that reason.
To locate all the specializations of Sets, the rippling would go in
the opposite direction. For example, one of the entries on the
Specializations facet of Sets is Set-of-structures; one if ⊗4its⊗*
Specialization entries is Set-of-sets. So this latter concept will be
caught in the net when rippling away from Sets in the Specializations
direction.
If AM wants lots of examples of sets, it has only to ripple in the
Specializations direction, gathering Examples of each concept it
encounters. Examples of Sets-of-sets (like this one: {{A},{{C,D}}}})
will be caught in this way, as will examples of Set-of-numbers (like
this one: {1,4,5}), because two specializations of Sets are
Sets-of-Sets and Sets-of-Numbers$$ We are assuming that AM has run
for some time, and already discovered Numbers, and already defined
Sets-of-Numbers. $.
In addition to the three main reasons for keeping the set of facets fixed
(see previous page), there are several small reasons for not dynamically enlarging it.
To add a new facet, its value has to be filled in for lots of concepts.
How could AM develop the huge body of heuristics needed to guide such
filling-in and checking activities? Also, the number of facets is small
to begin with because people don't seem to use more than a few tens of
such "properties" in classifying knowledge about a concept$$ This data
is gathered from introspection by myself and a few others, and should probably
be tested by performing some psychological experiments. $.
If the viabilitiy of AM seemed to depend on this abilitiy, I would have worked
on it. AM got along fine without being able to enlarge its set of facets, so
no time was ever spent on that problem.
I leave it as a challenging, ambitious "open research problem"$$ i.e., a
limitation of the AM system. $.
. SSSEC(BEINGs Representation of Knowledge)
Before discussing each facet in detail, let's inteject a brief
historic digression, to explain the origins of this modular representation scheme.
<< Summarize the ideas and the PUP6 implementation of BEINGs scheme. 1-page. >
.SSEC(Facets)
How ⊗4is⊗* each concept
represented?
Without claiming that this is the "best" or preferred scheme, this section
will present a detailed answer.
.FACETSSEC: SSECNUM;
.FACETPAGE: PAGE;
We have seen that the representation of a concept can loosely be
described as a collection of facet/value pairs, where the facets are
drawn from a fixed set of about 25 total possible facets.
The facets break down into two categories:
.BN
λλ Facets which relate this concept C to some other one(s):
Generalizations, Specializations, Examples, Isa's, In-domain-of,
In-range-of, Views, Intu's, Analogies, Conjec's
λλ Facets which contain information intensive to this concept C:
Definitions, Algorithms, Domain/Range, Worth, Interest, Suggest, Fillin, Check
.E
Some facets come in several flavors (e.g., there are really four
separate facets -- not 1 -- which point to examples: boundary,
typical, just-barely-failing, foibles).
.GROUP
This section will cover each facet in turn. Let's begin by listing
each of them. For a change of pace, we'll show a typical question
that each one might answer about concept C:$$ In this discussion, "C"
represents the name of the concept whose facet is being discussed,
and may be read "the given concept". $
.SKIP 1 BN
Name: What shall we call C when communicating with the user?
Generalizations: Which other concepts have less restrictive definitions than C?
Specializations: Which concepts satisfy C's definition plus some additional
constraints?
Examples: What are some things that satisfy C's definition?
Isa's: Which concepts' definitions does C itself satisfy?$$ Notice that C will
therefore be an example of each member of Isa's(C). Got that?$
In-domain-of: Which operations can be performed on C's?
In-range-of: Which operations result in values which are C's?
Views: How can we view a C as something else?
Intu's: What is an abstract, analogic representation for C?
Analogies: Are there similar (though formally unrelated) concepts?
Conjec's: What are some potential theorems involving C?
Definitions: How can we tell if x is an example of C?
Algorithms: How can we execute the operation C on a given argument?
Domain/Range: What kinds of arguments can operation C be executed on? What kinds of
values wil it return?
Worth: How valuable is C? (overall, aesthetic, utility, etc.)
Suggest: If AM gets bogged down, what are some new tasks (related to C)
it might consider?
.E
In addition, each facet F of concept C can possess a few little subfacets which
contain heuristics for dealing with that facet of C's:
.bn SKIP 1
F.Fillin: How can entries on C.F be filled in?
These heuristics get called on when the current task is ⊗6"Fillin
facet F of concept X"⊗*, where X is a C.
F.Check: How can potential entries on C.F be checked and patched up?
F.Interestingness: What special features make some entries on C.F especially
interesting?
.E
.SS1←SSECNUM+1;
.ONCE TURN ON "{}"
We'll now begin delving into the syntax and semantics of each facet,
one by one. Future chapters will not depend on this material. The
reader may wish to skip to Section {SECNUM}.{SS1} (page {[3]CDIAG}).
. SSSEC(Generalizations/Specializations)
We say "⊗4concept A is a generalization of⊗*" concept B iff
every example of B is an example of A. Equivalently, this is true iff
the definition of B can be phrased as "λ (x) [A.Defn(x) and P(x)]";
that is, for x to satisfy B's definition, it must satisfy A's definition plus
some additional predicate P.
The Generalizations facet of C does not contain ⊗4all⊗* generalizations of
C; rather, just the "immediate" ones. More formally, if A is a generalization
of B, and B of C, then C.Genl will ⊗4not⊗* contain a pointer to A.
Instead, C will point to B$$ In general,
C.Genl will contain an entry X1; X1.Genl will contain an entry X2;...;
Xn.Genl will contain B as one entry; B.Genl will contain Y1;...; Yn.Genl will
contain A. $.
We can restate this one more time: The graph of Spec links should$$
Cycles are merely "redundant" links, and they are permitted to exist if
they speed up some algorithm, if they represent a path which is frequently
asked about. This is described in more detail on the page {[3]TRICK}. $
contain no cycles, and the graph of just Genl links should contain no cycles.
.GROUP
The format of the Generalizations facet is quite simple: it is a list of
concept names. The Generalizations facet for Odd-primes might be:
.B816
(Odd-numbers Primes)
.E APART GROUP
Here is a small diagram representing generalization relationships. The only lines
drawn represent the pointers found in the Generalizations facets of these concepts:
.B0 INDENT 25
Object
\
\
\
\
\
\
Number
/ \
/ \
/ \
/ \
/ \
/ \
Odd-numbers Primes
\ / \
\ / \
\ / \
\ / \
\ / \
\ / \
Odd-primes Even-primes
\
\
\
\
\
\
Mersenne-primes
.E
For example, we see that the Generalizations facet of Odd-primes contains
pointers to both Odd-numbers and to Primes.
There is no pointer from Odd-primes to Number, because
there is an "intermediate" concept (namely, Primes).
.APART
The reason for these strange constraints is so that the total number of links
can be minimized. There is no harm if a few redundant ones sneak in.
In fact, frequently-used paths are granted the status of single links, as we
shall soon see.
We've been talking about both Specializations and Generalizations as if they were
very similar to each other. It's time to make that more explicit:
Specializations are the converse of Generalizations. The format is the same, and
(hopefully) A is an entry on B's Specializations facet iff B is an entry on
A's Generalizations facet. These facets will be abbreviated Spec and Genl.
The uses of these two facets are many:
.BN
.TURN ON "{}"
λλ AM can sometimes establish independently that A is both a generalization and
a specialization of B; in that case, AM would like to
recognize that fact easily, so it can
conjecture that A and B specify
equivalent concepts. Such coincidences are easily detected as ⊗4↓_cycles_↓⊗* in the
Genl (or Spec) graph.
In these cases, AM may physically merge A and B into one concept.
λλ Sometimes, AM wants to assemble a list of all specializations (or
generalizations) of X, so that
it can test whether some statement which is just barely true (or false) for X
will hold for any of those specializations of X.
λλ Sometimes, the list of generalizations is used to assemble a list of
isa's; the list of specializations helps assemble a list of examples.
This process will be described in great detail in Appendix {[2]RIPPLE}.
λλ A common and crucial use of the list of generalizations is to locate all the
heuristic rules which are relevant to a given concept. Typically, the relevant
rules are those tacked onto Isa's of that concept, and the list of Isa's is built up
from the list of generalizations of that concept.
This was also mentioned on page {[3] GENLSPEC}, and will be described in
Appendix {[2]RIPPLE}.
λλ To incorporate new knowledge. If AM learns, conjectures, etc. that A is a
specialization of B, then all the machinery (all the theorems, algorithms, etc.)
for B become available for working with A.
.E
<<Should we illustrate each of these uses of Genl/spec facets?>
.TRICK: PAGE;
Here is a little trick that
deserves a couple paragraphs of its own. AM stores the answers to common questions
(like "What are ⊗4all⊗* the specializations of Operation") explicitly,
by intentionally permitting redundant links to be maintained.
If two requests arrive closely in time, to test whether A is a generalization
of B, then the result is stored by adding "A"
as an entry on the Generalizations facet of
B, and adding "B" as a new entry on
the Specializations facet of A.
The slight extra space is more than recompensed in cpu time saved.
If the result were False (A turned out not to be a generalization of B) then the
links would specify that finding explicitly,
so that the next request would not generate a long search again.
Such failures are recorded on two additional facets: Genl-not and Spec-not.
Since most concept pairs A/B are related by Spec-not and by Genl-not,
the only entries which get recorded here are the ones which were frequently
called for by AM. If space ever gets tight, all such facets can be
wiped clean with no permanent damage done.
These two "shadow" facets (Genl-not and Spec-not) are not useful or interesting
in their own right.
If AM ever wished to know all
the concepts which are ⊗4not⊗* generalizations of C, the fastest way would
be to take the set-difference of all concepts and Generalizations(C).
Since they are quite incomplete, these facets are used more like a cache
memory: they save time whenever they are applicable, and don't really cost
much when they aren't applicable.
Because of their superfluity, these two facets will not be mentioned again.
I only mentioned them above because they do greatly speed up AM's execution
time, and because they may have some psychological analog.
. SSSEC(Examples/Isa's)
.ONCE TURN ON "{}"
We say "⊗4concept A is an example of concept B⊗*" iff
A satisfies B's definition.$$
What does this mean? B.Defn is a Lisp predicate, a Lambda expression.
If it is fed A as its argument, then this means that
it will return True.
$ Equivalently, we say that "⊗4A isa B⊗*".
It would be legal (in that situation) for "A" to be an entry on
B.Exs (the Examples facet of concept B) and for "B" to be an entry on
A.Isa (the Isa's facet of concept A).
The
Examples and Isa's facets
will be described in great detail in Appendix {[2]RIPPLE}; see
page {[3]EXISA}. This subsection will not bother duplicating all that material.
The Examples facet of C does not contain ⊗4all⊗* examples of
C; rather, just the "immediate" ones.
The examples facet of Numbers will not contain "11" since it
is contained in the examples facet of Odd-primes.
A "rippling" procedure is used to acquire a list of all examples of a given
concept. The basic equation is:
.B816
Examples(x) = Specializations(Exs(Specializations(x))
.E
.ONCE TURN ON "{}"
where Exs(x) is the contents of the examples facet of x.
Examples(x) represents the final list of all known items which satisfy
the definition of X. Examples(x) includes x, Exs(x), Exs(Exs(x)), etc.
Specializations(x) might be more regularly written Spec↑*(x). That is,
all members of x.Spec, all members of ⊗4their⊗* Spec facet, etc.
Note the similarity of this to the formula for Isa's(x), given on page {[3]GIGPAGE}.
As an illustration, we shall show how AM would recognize that "3" is an example
of Object:
.B0 INDENT 25
Object
\
\
\
\
\
\
Number
/ \
/ \
/ \
/ \
/ \
/ \
Odd-numbers Primes
\ /
\ /
\ /
\ /
\ /
\ /
Odd-primes
\
\
\
\
\
\
Mersenne-primes
α⊗
α⊗
α⊗
3
.E
As the graph above shows, AM would ripple in the Spec direction 4 times,
moving from Object all the way to Mersenne-primes; then descend once in the
Exs direction, to reach "3"; then ripple 0 more times in the Spec direction.
Thus "3" is seen to be an example of Object, according to the above formula.
Similarly, we see that "3" is also an example of Number, of Primes, of Odd-number,
of Odd-primes, and of course an example of Mersenne-primes.
As with Generalizations/Specializations, the reasons behind the
incomplete pointer structure is simply to save space, and to minimize the
difficulty of updating when new links are found.
Suppose a new Mersenne prime$$
"Mersenne prime", without a hyphen, refers to a number satisfying certain properties
[see glossary].
"Mersenne-primes", with a hyphen, refers to one specific AM concept,
a data structure with facets. Each Mersenne prime is an example of the
concept Mersenne-primes. $
is computed. Wouldn't it be nice simply to add a
single entry to the Exs facet of Mersenne-primes, rather than to have to update the
Exs pointers from a dozen concepts?
There is no harm if a few redundant links sneak in.
In fact, frequently-used paths are granted the status of single links.
If two requests arrive closely in time, to test whether A isa
B, then the result is stored as an entry on the Isa facet of
A, and the Exs facet of B. If the result were False, then the
links would specify that, so that the next request would not generate a long search.
In fact, there is a separate facet called Exs-not, and one called Isa-not.
These two shadowy facets are quite analogous to the unmentionable facets
"Genl-not" and "Spec-not", discussed in the previous subsection.
"Isa's" is the converse of "Examples". The format is the same, and
(if A and B are both concepts) A is an entry on B.Isa iff B is an entry on
A.Exs. In other words, A is a member of Examples(B) iff B is a member of
Isa's(A). Due to an ugly lack of standardization, non-concepts are allowed to
exist. Thus, "3" is an example of Primes, but is not itself a concept.
Examples of X sometimes are concepts, of course: "Intersect-o-Intersect" is an
example of Compose-with-self.
And Isa's(x) are always concepts.
The highest level concept is called "Anything". Its definition is the
atom T. That is, "λ(x) T". This high-level concept can claim everything as
its examples.
The ⊗4uses⊗* of the Exs/Isa's facets are similar to those for Genl/Spec
(see previous subsection).
Their formats are quite a bit more complicated than
the Genl/Spec facets' formats, when we finally get to the
implementation level, however.
There are really a cluster of different facets all related to Examples:
.SKIP 1 BN
λλ TYPICAL: This is a list of average examples. Care must be taken to include a wide
spectrum of allowable kinds of examples.
For "Sets", these would include sets of varying
size, nesting, complexity, type of elements, etc.
λλ BOUNDARY: Items which just barely pass the definition of this concept. This might
include items which satisfy the base step of a recursive definition, or items which
were intuitively believed to be ⊗4non⊗*-examples of the concept.
For "Sets", this
might include the empty set.
λλ BOUNDARY-NOT: Items which just barely fail the definition. This might include an
item which had to be slightly modified during checking, like α{A,B,Aα} becoming
α{A,Bα}.
λλ FOIBLES: Total failures. Items which are completely against the grain of this
concept. For "Sets", this might include the operation "Compose".
λλ NOT: This is the "cache" trick used to store the answers to frequently-asked
questions. If AM frequently wants to know whether X is an example of Y, and
the answer is ⊗4No⊗*, then much time can be saved by adding X as an entry to the
Exs-not facet of Y.
.E
An individual item on these facets may just be a concept name, or it may be
more complicated.
In the case of an operation, it is an item of the form <a↓1a↓2...→v>; i.e., actual
arguments and the value returned. In the case of objects, it is an object of
that form. An Exs facet of the concept Sets might contain {a} as one entry.
Here is a more detailed illustration. Consider the
Examples facet of Set-union. It might appear thus:
.B816 TURN OFF "{}" GROUP TURN ON "\" TABS 25
TYPICAL: {A}∪{A,B}→{A,B};
\{A,B}∪{A,B}→{A,B};
\{A,<3,4,3>,{A,B}}∪{3,A}→{A,<3,4,3>,{A,B},3}.
BOUNDARY: {}∪X→X $$
Actually, AM is not quite smart enough to use the variable X as shown in the
boundary examples. It would simply store a few instances of this general rule, plus
have an entry of the form <Equivalent: Identity(X) and Set-union(X,α{α})> on the
Exs facet of Conjectures.
Notice that because of the asymmetric way Set-union was defined,
only one lopsided boundary example was found. If another definition were supplied,
the converse kind of boundary examples would be found. $
BOUNDARY-NOT: {A,B}∪{A,C}={A,B,A,C};
\{A,B,C,D}∪{E,F,G,H,I,J}={A,B,C,E,F,G,H,I,J}
FOIBLES: <2,A,2>
NOT: no entries
.E
The format for Isa's are much simpler:
there are only two kinds of links, and they're each merely a
list of concept names.
Here is the Isa facet of Set-union:
.B816 GROUP
ISA: (Function Domain=Range-relation)
ISA-NOT: (Structure Composition)
.E
At some time, some rule asked whether Set-union ↓_isa_↓ Composition. As a result,
the negative response was recorded by adding "Composition" to the Isa-not
facet of Set-union, and adding "Set-union" to the Exs-not subfacet of the
Examples facet of the concept Composition
(indicating that Set-union was definitely not an
example of Composition, yet there was no reason to consider it a foible).
. SSSEC(In-Domain-of/In-Range-of)
.COMMENT: WARNING: DON'T CENTER!!!;
We shall say that A is in the domain of B (written "A In-dom-of B")
iff
.BN
λλ A and B are concepts
λλ B isa Operation
λλ A is equal to (or at least a
specialization of) one of the domain components of the operation B. That is,
B can be executed using any example of A as one of its arguments.$$
More formally, we can say that this occurs whenever
some entry on the Domain/range facet of B has the form <D↓1
D↓2... D↓i → R> with some D↓j a member of Generalizations(A). Then A
is a specialization of some domain component of some entry on
B.Domain/range. $
.E
For example, Odd-perfect-squares is In-dom-of Squaring, since
Odd-perfect-squares is a specialization of Numbers,
and Numbers is one component of the following entry which is located on
Squaring.Domain/range: <Numbers → Numbers>. In fact, Numbers is the ⊗4only⊗*
such domain component. Since Odd-perfect-squares is a specialization of Numbers,
the operation of Squaring can be executed using any example of Odd-perfect-squares
as its argument. Incidentally, if this is done, then the result will be a perfect
fourth power.
As another
example, Odd-perfect-squares is also In-dom-of Set-insert,
one of whose Domain/range
entries is <Anything Sets → Sets>. This is because
Odd-perfect-squares is a specialization of Anything.
So Set-insert is executed on two arguments, and the first argument can be
any example of Odd-perfect-squares (the second argument must be an example of
Sets).
Although it can be recomputed very easily, we may wish to record the
fact that A In-dom-of B by adding the entry "B" to the In-dom-of
facet of A. AM may even wish to add this new entry to the
Domain/range facet of B:
.ONCE PREFACE 0
< D↓1 D↓2... D↓j↓-↓1 A D↓j↓+↓1... D↓i → R>.
The two examples given above would produce new domain/range entries of
<Odd-perfect-squares → Numbers> for Squaring, and <Odd-perfect-squares
Sets → Sets> for Set-insert.
The semantic content of "In-dom-of" is: what can be done to
any example of
a given
concept C? Given an example of concept C, what operations can be
run on that thing? Here are some illustrations:
.BN
"Odd-perfect-squares In-dom-of Set-insert" tells us that Set-insert
can be run on any particular Odd-perfect-square we can grab hold of.
"Operation In-dom-of Compose" tells us that Compose can be run on any
operation we want.
"Dom=Range-operation In-dom-of Compose" tells us that Compose can be
run on any operation which has its range equal to one of its domain
components.
"Primes In-dom-of Squaring" tells us that we can apply the operation
Squaring to any particular prime number we wish.
.E
Let us now turn from In-dom-of to the related facet In-ran-of.
We say that concept A is in the range of B iff B is an Activity$$
i.e., iff B isa Active, iff BεExamples(Active), iff Active.Defn(B)=True.
Actually, since the range of Predicates is merely α{T,Fα}, we may as well assume that
B is an operation, not a predicate. This is in fact assumed, in the text and in
the actual AM system. $
and A is a specialization of the range of B. More precisely,
we can say that "A In-ran-of B" iff
.BN
λλ A and B are concepts
λλ B isa Operation (i.e., B is an example of the concept "Operation")
λλ Some entry on the Domain/range facet of B has the form <D↓1
D↓2... D↓i → R> with R a generalization of A.
.E
For example, Odd-perfect-squares is In-ran-of Squaring, since (1) both of
those are concepts, (2) Squaring is an operation, (3) one of its Domain/range
entries is <Numbers→Perf-squares>, and
Perf-squares is a generalization of Odd-perfect-squares$$ Why? Because
Generalizations(Odd-perfect-squares) is the set of concepts
α{Odd-numbers Perf-squares Numbers Objects Any-concept Anythingα},
hence contains Perf-squares.
So Perf-squares is a generalization of Odd-perfect-squares. $.
Here is what the In-ran-of facet of Odd-perfect-squares might look
like:
.B816
(Squaring Add TIMES Maximum Minimum Cubing)
.E
Each of these operations will -- at least
sometimes -- produce an odd perfect square
as its result.
Semantically, the In-ran-of relation between A and B means that one
might be able to produce examples of A by running operation B. Aha!
This is a potential mechanism for finding examples of a concept A.
All you need do is get hold of In-ran-of(A), and run each of those
operations. Even more expeditious is to examine the Examples facets
of each of those operations, for already-run examples whose values
should be tested using A.Defn, to see if they are examples of A's.
AM relies on this in times of high motivation; it is too "blind" a
method to use heavily all the time.
This facet is also useful for generating situations to investigate.
Suppose that the Domain/range facet of Doubling contains only one
entry: < Numbers → Numbers >. Then syntactically, Odd-numbers is in the
range of Doubling. Eventually a heuristic rule may have AM spend some
time looking for an example of Doubling, where the result was an odd
number. If none is quickly found, AM conjectures that it ⊗4never⊗* will be
found. Since one definition of Odd-number(x) is "Number(x) and
Not(Even-number(x))", the only non-odd numbers are even numbers. So
AM will increment the Domain/range facet of Doubling with the entry
<Numbers→Even-numbers>, and remove the old entry. Thus Odd-numbers
will no longer be In-dom-of Doubling. AM can of course chance upon
this conjecture in a more positive way, by noticing that all known
examples of Doubling have results which are examples of Even-numbers.
.BEGIN XGENLINES←XGENLINES-1;
.SEND FOOT ⊂ TURN ON "[]{" SELECT 7; SPACING 0; PREFACE 0; INDENT 0,10
⊗A6⊗* Wrong. That was an exponent, not a footnote!
.BREAK ⊃
.CONTINUE END CONTINUE;
$$ This
positive approach is in fact the way AM noticed this particular relationship. $.
A more productive result is suggested by examining the cases where
Odd-perfect-squares are the result of cubing. The smallest such odd
numbers are 1, 729, and 15625. In general, these numbers are all those of
the form (2n+1)↑6. How could AM notice such an awkward relationship?
The general question to ask, when A In-ran-of B,
is "What is the set of domain items whose values (under the operation
B) are A's?" In case the answer is "All" or "None", some special
modifications can be made to the Domain/range facets and In-dom-of,
In-ran-of facets of various concepts, and a new conjecture can be
printed. In other cases, a new concept might get created,
representing precisely the set of all arguments to B which yield
values in A. If you will, this is the inverse image of A, under
operation B. In the case of B a predicate, this might be the set of
all arguments which satisfy the predicate.
In the case of B=Cubing
and A=Odd-perfect-squares, the heuristic mentioned above will have
AM create a new concept:
the inverse image of Odd-perfect-squares under the operation of Cubing.
That is, find numbers whose cubes are Odd-perfect-squares.
It is quickly noticed that such numbers are precisely the set of
Odd-perfect-squares themselves! So
The Domain/range facet of Cubing might get this new entry:
<Odd-perfect-squares → Odd-perfect-squares>.
But not all squares can be reached by cubing, only a few of them can.
AM will notice this, and
the new range would then be isolated and might be renamed
by the user "Perfect-sixth-powers". Note that all this
was brought on by examining the In-ran-of facet of
Odd-perfect-squares. "Cubing" was one of the seven syntactically
allowable entries there. There are six more stories to tell in this
tiny nook of AM's activities.
How exactly does AM go about gathering the In-ran-of and In-dom-of
lists? Given a concept C, AM can scan down the global tree of operations
(the Exs and Spec links below the concept Operation).
For if C is not In-dom-of F, it certainly won't be In-dom-of any
specialization of F. Similarly, if it can't be produced by F, it
won't be produced by any specialization of F. If you can't get X
using TIMES, you'll never get it by Squaring. So AM simply ripples
around, as usual. The precise code for this algorithm is of little
interest. There are not that many operations, and it is cheap to
tell whether X is a specialization of a given concept, so even an
exhaustive search wouldn't be prohibitive. Finally, recall that such
a search is not done all the time. It will be done initially,
perhaps, but after that the In-dom-of and In-ran-of networks will
only need slight updating now and then.
. SSSEC(Views)
Often, two concepts A and B will be inequivalent, yet there will be a "natural"
bijection between one and (a subset of) the other.
For example, consider a finite set S of atoms, and consider the
set of all its subsets, 2↑S,
also called the ⊗4power set⊗* of S.
Now S is a member of, but not a ⊗4subset⊗* of, 2↑S
(e.g., if S={x,y,...}, then x is not a member of 2↑S).
On the other hand, we can identify or view
S as a subset by the mapping x→{x}. Then S is associated with the following
subset of 2↑S: { {x}, {y},... }. Why would we want to do this? Well, it shows
that S is identified with a ⊗4proper⊗* subset of 2↑S, and indicates that S has
a lower cardinality (remember: all sets are finite).
As another example, most of us would agree that the set {x, {y}, z} can be
associated with the following bag: (x, {y}, z). Each of them can be viewed as
the other. Sometimes such a viewing is not
perfectly natural, or isn't
really a bijection: how could
the bag (2, 2, 3) be viewed as a set? Is {2,3} better or worse than
{2,{2},3)?
The View facet of a concept C describes how to view instances of another concept D
as if they were C's. For example, this entry on the View facet
of Sets explains how to view any given structure as if it were a Set:
.B816
Structure: λ (x) Enclose-in-braces(Sort(Remove-multiple-elements(x)))
.E
If given the list <z,a,c,a>, this little program would remove
multiple elements (leaving <z,a,c>), sort the structure
(making it <a,c,z>), and replace the "<...>" by "{...}", leaving the
final value as {a,c,z}. Note that this transformation is not 1-1; the
list <a,c,z> would get transformed into this same set.
On the other hand, it may be more useful than transforming
the original list into {z,{a,{c,{a}}}} which retains the ordering and
multiple element information.
Both of those transformations may be present as entries on the View
facet of Sets.
As it turns out, the View facet of Sets actually contains only the following
information:
.B816
Structure: λ (x) Enclose-in-braces(x)
.E
Thus the Viewing will produce entities which are not quite sets. Eventually,
AM will get around to executing a task of the form "Check Examples of Sets",
and at that time the error will be corrected.
One generalization of Sets is No-multiple-elements-Structures, and one of its
entries under Check says to remove all multiple elements. Similarly,
Unordered-structures is a generalization of Sets, and one of its Check facet entries
says to sort the structure. If either of these alters the structure, the old structure
is added to the Just-barely-miss kind of Examples facet of Sets.
The syntax of the View facet
of a concept C
is a list of entries; each entry specifies the name of
a concept, X, and a little program P. If it is desired to view an instance of
X as if it were a C, then program P is run on that X; the result is (hopefully)
a C. The programs P are opaque to AM; they must have no side effects and be quick.
Here is an entry on the View facet of Singleton:
.B816
Anything: λ (x) Set-insert(x, PHI)
.E
In other words, to view anything as a singleton set, just insert it into the
empty set. Note that this is also one way to view anything as a set. As you've
no doubt guessed, there is a general formula explaining this:
.ONCE CENTER PREFACE 0 SELECT 6
Views(X) ≡ View(Specializations(X))
Thus, to find all the ways of viewing something as a C, AM ripples away from C
in the Spec direction, gathering all the View facets along the way.
All of their entries are valid entries for C.View as well.
.GROUP
In addition to these built-in ways of using the Views facets, some special
uses are made in individual heuristic rules.
Here is a heuristic rule which employs the Viewing facets of relevant concepts in
order to find some examples of a given concept C:
.B816
.ONCE INDENT 4
IF the current task is to Fill-in Examples of C,
and C has some entries on its View facet,
and one of those entries <X,P> indicates a concept X which has some known Examples,
.ONCE INDENT 4
THEN run the associated program P on each member of Examples(X),
and add the following task to the agenda: "Check Examples of C", for the
following reason: "Some very risky techniques were used to find examples of C",
and that reason's rating is computed as:
Average(Worth(X), ||the examples of C found in this manner||).
.E
.APART
Say the task selected from the agenda was "Fill-in Examples of Sets".
We saw that one entry on Sets.View was ⊗6Structure: λ(x) Enclose-in-braces(x)⊗*.
Thus it is of the form <X,P>, with X=Structure. The above heuristic rule will
trigger
if any examples of Structures are known. The rule will then use the
View facet of Sets to find some examples of Sets.
So AM will go off, gathering all the examples of structures.
Since Lists is a Specialization of
Structure, the computation of Examples(Structures) will eventually ripple
downwards and ask for Examples of Lists. If the Examples facet of Lists
contains the entry <z,a,c,a,a>, then this will be retrieved
as one of the members of Examples(Structure). The heuristic rule takes each such
member in turn, and
feeds it to Set.View's
little program P.
In this case, the program replaces the list brackets with set braces, thus converting
<z,a,c,a,a> to α{z,a,c,a,aα}.
In this manner, all the existing structures will be converted
into sets, to provide examples of sets.
After all such conversions take place, a great number
of potential examples of Sets will exist. The final action of the right side of the
above heuristic rule is to add the new task "⊗6Check examples of Sets⊗*" to the
agenda. When this gets selected, all the "slightly wrong" examples will be fixed
up. For example, {z,a,c,a,a} will be converted to {a,c,z}.
If any reliance is made on those unchecked examples, there is the danger of
incorrectly rejecting a valid conjecture. This is not too serious, since the
very first such reliance will boost the priority of the task
"⊗6Check examples of Sets⊗*", and it would then probably be the very next task
chosen.
. SSSEC(Intuitions)
[Errata: please replace the word ⊗4"Intuition"⊗*, wherever it exists
in this document, by the word "G00035" -- dbl]
This facet turned out to be a "dud", and was later excised from all
the concepts. It will be described below anyway, for the benefit of
future researchers. Feel free to skip directly to the next
subsection.
The initial idea was to have a set of a few (3-10) large, global,
opaque LISP functions. Each of these functions would be termed an
"Intuition" and would have some suggestive name like "jigsaw-puzzle",
"see-saw", "archery", etc. Each function would somehow model the
particular activity implied by its name. There would be a multitude
of parameters which could be specified by the "caller" as if they
were the arguments of the function. The function would then work to
fill in values for any unspecified parameters. That's all the
function does. The caller would also have to specify which
parameters were to be considered as the "results" of the function.
For the see-saw, the caller might provide the weight of the
left-hand-side sitter, and the final position of the see-saw, and ask
for the weight of the right-hand sitter. The function would then
compute that weight (as any random number greater/less-than the
left-hand weight, depending on the desired tilt of the board). Or,
the caller might specify the two weights and ask for the final
position.
The See-saw function is an expert on this subject; it has
efficient code for computing any values which can be computed, and
for randomly instantiating any variables which may take on any value
(e.g., the first names of the people doing the sitting). When an individual
call is made on this function, the caller is not told how the final values
of the variables were computed, only what those values end up as.
So the Intuitions were to be experimental laboratories for AM,
wherein it could get some (simulated) real-world empirical data. If
the seesaw were the Intuition for ">", and weight corresponded to
Numbers, then several relationships might be visualized intuitively
(like the anti-symmetry of ">"). This is a nice idea, but in practice
the only relationships derived in this way were the ones that were
thought up while trying to encode the Intuition functions. This
shameful behavior led to the excision of the Intuitions facets
completely from the system.
As another example, suppose AM is considering composing two relations
R and S. If they have no common Intuition reference, then perhaps
they're not meaningfully composable. If they do both tie into the
same Intuition function, then perhaps that function can tell us
something about the composition. This is a nice idea, but in practice
very few prunings were accomplished this way.
Each Intuition entry is like a "way in" to one of the few global
scenarios. It can be characterized as follows:
.BN
λλ One of the sailent features of these entries -- and of the
scenarios -- is that AM is absolutely forbidden to look inside them,
to try to analyze them. They are ⊗4↓_opaque_↓⊗*. Most Intuition
functions use numbers and arithmetic, and it would be pointless to
say that AM discovered such concepts if it had access to those
algorithms all along.
λλ The second characteristic of an Intuition is that it be
⊗4↓_fallible_↓⊗*. As with human intuition, there is no guarantee
that what is suggested will be verified even empirically, let alone
formally. Not only does this make the programming of Intuition
functions easier, it was meant to provide a degree of "fairness" to
them. AM wasn't cheating quite as much if the See-saw function was
only antisymmetric 90% of the time.
λλ Nevertheless, the intuitions are very ⊗4↓_suggestive_↓⊗*. Many
conjectures can be proposed only via them. Some analogies (see the
next subsection) can also be suggested via common intuitions.
.E
After they were coded and running, I decided that the intuition
functions were unfair; they contained some major discoveries
"built-in" to them. They had the power to magically suggest
otherwise obscure potential relationships.
Due
to the paucity of the contribution by AM's few Intuition functions,
they were removed from the system. All the examples and all the
discoveries listed in this document were made without their
assistance.
We shall now drop this de-implemented idea. I think there is some
real opportunity for research here; it is what you get$$ Notice the
careful wording here. $ for reading the thesis in this much detail!
As a hint to future research in this area, let me point to the excellent
discussion of analogic representations in [Sloman Philos&AI].
. SSSEC(Analogies)
As with Views and Intuitions, this facet is useful for shifting
between one part of the universe and another. Views dealt with
transformations between two specific concepts; Intuitions dealt with
transformations between a bunch of concepts and a large standard
scenario which was carefully hand-coded in advance. In contrast,
this facet deals with transforming between a list of concepts and
another list of concepts.
Analogies operate on a much grander scale than Views. Rather than
simply transforming a few isolated items, they initiate the creation
of many new concepts. Unlike Intuitions, they are not limited in
scope beforehand, nor are they opaque. They are dynamically proposed.
The concept of "prime numbers" is ⊗4analogous⊗* to the notion of
"simple groups"$$
If a group is not simple, it can be factored.
Unfortunately, the factorization of a group into simple groups is not unique.
Another analogizing contact: For each prime p, we can
associate the cyclic group of order p, which is of course simple. $
While not isomorphic, you might guess at a few relationships
involving simple groups just by my telling you this fact:
simple groups are to groups what primes are to numbers.
Let's take 3 elementary examples, involving very fundamental
concepts.
.XGENLINES←XGENLINES-1
.skip 1 BN PREFACE 1
λλ AM can ↓_View_↓ a set as if it were a bag.
λλ AM once ↓_Intuit_↓ed the relation "⊗6≥⊗*" as the predetermined "See-saw"
function.
λλ AM once ↓_Analogize_↓d that these two lists correspond:
.TABS 11, 24, 37 TURN ON "\" PREFACE 0
\<Bags\Same-length\Operations-on-and-into Bags>
\<Bags-of-T's\Equality\Those operations restricted to Bags-of-T's>
.E
.XGENLINES←XGENLINES-1
The concept of a bag, all of whose elements are "T"'s, is the unary
representation of ⊗4numbers⊗* discovered by AM. When the above
analogy (#3) is first proposed, there are many known Bag-operations$$
i.e., all entries on In-dom-of(Bag) and In-ran-of(Bag); a few of
these are: Bag-insert, Bag-union, Bag-intersection$, but there are as
yet no numeric operations$$ Examples of Operation whose domain/range
contains "Number". $. This triggers one of AM's heuristic rules, which
spurs AM on to finding the analogues of specific Bag-operations. That
is, what special properties do the bag-operations have when their
domains and/or ranges are restricted from Bags to Bags-of-T's (i.e,
Numbers). In this way, in fact, AM discovers Addition (by
restricting Bag-union to the Domain/range <Bags-of-T's Bags-of-T's →
Bags-of-T's>), plus many other nice arithmetic functions.
Well, if it leads to the discovery of Addition, that analogy is
certainly worth having. How would an analogy like that be proposed?
As usual, it is simply some heuristic rule, adding it as an entry to
the Analogies facet of a certain concept. For example:
.B816 INDENT 4,16,0
IF the current task has just created a canonical specialization C2 of
concept C1, with respect to operations F1 and F2, [i.e., two members
of C2 satisfy F1 iff they satisfy F2],
THEN add the following entry to the Analogies facet of C2:
.TABS 24,30,36 TURN ON "\"
\<C1\F1\Operations-on-and-into(C1)>
\<C2\F2\Those operations restricted to C2's>
.E
After generalizing "Equality" into the operation "Same-length", AM
.B816 INDENT 4,16,0
IF the current task has just created a canonical specialization C2 of
concept C1, with respect to operations F1 and F2, [i.e., two members
of C2 satisfy F1 iff they satisfy F2],
THEN add the following entry to the Analogies facet of C2:
.TABS 24,30,36 TURN ON "\"
\<C1\F1\Operations-on-and-into(C1)>
\<C2\F2\Those operations restricted to C2's>
.E
After generalizing "Equality" into the operation "Same-length", AM
seeks to find a canonical$$ A natural, standard form. All bags
differing in only "unimportant" ways should be transformed into the
same canonical form.
Two bags B1 and B2 which have the same length should get transformed into
the same canonical bag.
$ representation for Bags. That is, AM seeks a
canonizing function f, such that (for any two bags x,y)
.B816
⊗6Same-length(x,y) iff Equal( f(x), f(y) ).⊗*
.E
Then the range of f would delineate the set of "canonical" Bags. AM
finds such an f and such a set of canonical bags: the operation
involves replacing each element of a bag by "T", and the canonical
bags are those whose elements are all T's. In this case, the above
rule triggers, with C1=Bags, C2=Bags-of-T's, F1=Same-length,
F2=Equality, and the analogy which is produced is the one shown as
example #3 above.
The Analogy facets are not implemented in full generality in the
existing LISP version of AM, and for that reason I shall refrain from
delving deeper into their format. Since good research has already
been done on reasoning by analogy$$ An excellent discussion of
reasoning by analogy is found in [Polya]. Some early work on emulating
this was done by [Evans]; a more recent thesis on this topic is
[Kling]. $, I did not view it as a central feature of my work. Very
little space will be devoted to it in this document.
An important type of analogy which was untapped by AM was that
between heuristics. If two situations were similar, conceivably the
heuristics useful in one situation might be useful (or have useful
analogues) in the new situation. Perhaps this is a viable way of
enlarging the known heuristics. Such "meta-level" activities were
kept to a minimum throughout AM, and this
proved to be a serious limitation.
Let me stress that the failure of the Intuitions facets to be
nontrivial was due to the lack of spontaneity which they possessed.
Analogies facets were useful and "fair" since their uses were not
predetermined by the author.
. SSSEC(Conjec's)
Basically, the facet Conjec
of concept C is a list of
relationships which involve C.
We shall discuss its semantics (uses of this facet) before its syntax.
Perhaps the most obvious use for this facet would be to hold
conjectures which could not be phrased simply. Yet it turns out that
luckily (I think), all the conjectures "fell out" naturally as trivial
relationships,
i.e. simply as arcs in the Genl/Spec/Exs/Isas pointer format.
For example, the unique factorization conjecture is merely the
observation that Prime-factorings is not merely a relation but a function.
There is a concept called "Prime-factorings", whose Isa facet contains
the entry "Relation". A heuristic rule has AM check to see what the specializations
of Relation are; they include Function. Then AM checks to see if Prime-factorings
satisfies the definition of Function, not merely that of Relation.
It does, so the new entry "Function" is added to the Isa facet of Prime-factorings.
.ONCE TURN ON "{}"
In all the cases encountered by AM, there was never any real need for a place to
"park" an awkwardly-phrased conjecture, because ⊗4no awkward conjecture could ever
possibly be noticed⊗*. Why is this so?
AM was constructed explicitly on the assumption that
all (enough?) important theorems could be discovered in quite natural ways,
as very simple (already-known) relationships on already-defined concepts.
AM embodies several such assumptions about math research; they are collected and
packaged for display in Section
{[2]MODELSEC}.{[2]MODELSSEC}.{[2]MODELSSSEC}, on
page {[3]MODELPAGE}.
What else might this facet be useful for, if not the storage of awkwardly-worded
conjectures?
It might be a good place to store ⊗4flimsy⊗* conjectures: those which were
strong enough to get considered, yet for which not much empirical confirmation
had been done.
This in fact was one important role of this facet.
For example, AM was initially told that there are two specializations of
Unordered-structures, namely Bags and Sets. But AM was not given any examples
of any structures at all. Early on, it chose the task "Fillin examples of Bags"
from the agenda. After filling them in, a heuristic rule had AM consider whether
or not this concept of Bags was really any more specialized than the concept
of Unordered-structures. To test this empirically, AM tried to verify whether or
not there were any examples of Unordered-structures that were ⊗4not⊗* examples
of Bags. Failure to find any led to proposing the conjecture "All Unordered-structures
are really Bags". This could have been recorded quite easily:
Bags was already known to be specialization of Unordered-structure, so all AM
had to do was tag it as a generalization as well (add "Bags" to the
Generalizations facet of the Unordered-structures concept). But a heuristic
rule which knows about such equivalence conjectures first asked whether
there were any specializations of Unordered-structures which had no known
examples, and for which AM had not (recently, at least) tried to fill in examples.
In fact, such an entry was "Sets". So the conjecture was stored on the Conjec
facet of Unordered-structures, and a new job was added to the agenda:
"Fill in examples of Sets". The reason was that such examples might
disprove this flimsy conjecture. In fact, the job already existed on the
agenda, so only the new reason was added, and its priority was boosted.
When such examples were found, they did of course disprove that conjecture:
each set was an Unordered-structure and yet was not a Bag.$$
Bags are not multisets, although those two notions are very closely
related to each other. Each set is a multiset by definition; but each set is
guaranteed by definition to ↓_not_↓ be a bag. $
This last example has suggested another function for this facet: holding
heuristic rules which are relevant to filling in and checking conjectures.
For example, the Conjec facet of Operations has some special heuristics which
look for certain kinds of relationships involving any given operation
(e.g., "Pick any example F(x)=y. See what interesting statements can be made
about y. Then try to verify or disprove each one by looking at the values of
all the other known calls on operation F"). The Conjec facet of Any-concept
will contain more general knowledge
(e.g., "See whether concept C is an example of some member of (C.Isa).Spec").
Compose.Conjec will contain more
specific heuristics (e.g.,
"See if the composition A-o-B is really no different from
B").
Given any concept C, AM will ripple upwards, locating Isas(C), and collect
the heuristics which are tacked onto their Conjec facets. These heuristic rules
will then be evaluated (in order of increasing generality), and some conjectures
will probably be proposed, checked, discarded, modified, etc.
In fact, each Conjec facet of each concept can have two separate subfacets:
Conjec.Fillin and Conjec.Check. The former contains heuristics for noticing
conjectures, the second for verifying and patching them up.
There is yet another use for this facet, one of efficiency of storage.
After discovering that all primes except 2 are Odd-primes, there is very
little reason to keep around Odd-primes as a separate concept from Primes.
Yet they are not quite equivalent. Primes.Conjec is a good place for AM to
store the conjecture "Prime(x) implies that x=2 or Odd(x)", and to
pull over to Primes any efficient definition/algorithm which
Odd-primes might possess
(patching it up to work for "2"), and then destroy the concept Odd-primes.
Another way out is merely to destroy "Primes", and make 2 a distinguished
number tacked onto the Just-barely-missed subfacet of
Odd-primes.Exs (just like "1" is already).
Here is another example: AM discovers that Set-insert-o-Set-insert is
the same as just Set-insert. That is, if you insert x twice into a set S, it's
no different than inserting it just once (because Sets don't allow multiple
copies of the same element). Then there's no longer any reason for keeping
Set-insert-o-Set-insert hanging around as a separate concept.
Instead, just add a small new entry to Set-insert.Conjec and forget that
space-consuming composition forever.
There is another use of the Conjec facet: untangling paradoxes.
It is with no sorrow that
I mention that this facility was never needed by AM: no genuine contradictions
ever were believed by AM. What would one look like? Suppose a chain of
Spec links indicates that X is a specialization of Y, and yet AM finds some
example x of X which does not satisfy Y.Definition).
So X is -- and is not -- a specialization of Y.
In such cases, the Conjecs facets of the concepts involved would indicate
which of those Spec links were initially-supplied (hence unchallengable),
which links were created based on formal verifications (barely challengable),
and which links were established based only on empirical evidence (yes, these
are the ones which would then fade into the sunset).
If it has to, AM should be able to recall the justification for each new link
it created. AM can deduce this by examining the Conjec facets of the concepts
involved.
Periodically (at huge intervals) AM chose a task of the form
"Check conjecs about C", at which time all the entries on
C.Conjec
would be re-examined
in light of existing data. Some would be discarded
(perhaps causing some Exs/Isa/Spec/Genl links to vanish with them). Some of the
conjectures might be believed much more strongly now (causing some new links
to be recorded).
Finally, the Conjec's facet is used as a showcase,
to highlight some nice discovery that
AM wants to display. The user can look at the entries on each concept's Conjec
facet (after a long run) and get a better feeling for AM's abilities.
Let's recapitulate the uses of this facet:
.BN SKIP 1
λλ Store awkwardly-phrased conjectures: this wasn't really useful.
λλ Store flimsy conjectures: apparent
relationships worth remembering, yet not quite believed.
λλ Hold
heuristics which notice and check conjectures.
λλ Obviate the need for many similar concepts:
Collapse the entire essence of a related concept into one or two relationships
involving this one.
λλ Untangling paradoxes: a historic record, which wasn't really used.
λλ As a showcase into which the user can peer.
.E
The syntax of this facet is simply a list of conjectures, where each conjecture
has the form of a relationship: (R a b c...d). R is the name of a known operation
(in which case, abc... are its arguments and we claim that d is its value),
or R is a predicate (and d is either True or False), or R is the name of a kind of
link (Genl, Spec, Isa, or Exs), and the claim is that a and b are related by R.
Here are three example of conjectures, illustrating the possible formats:
.BN SKIP 1
λλ ⊗6(Compose Set-insert Set-insert Set-insert)⊗1. This says that if you apply
the known operation Compose, to the two arguments Set-insert and Set-insert,
then the resultant composition is indistinguishable from Set-insert.
λλ ⊗6(Same-size Insert(S,S) S False)⊗1. That is, inserting a set into itself
will always (for finite sets) give you a set of a different length.
λλ ⊗6(Exs Function Prime-factorings)⊗1. This conjecture is the unique factorization
theorem. The operation which takes a number n, and finds all prime factorizations
of n, is claimed to be a function, not merely a relation.
That is, each n has precisely one such prime factoring.
.E
. SSSEC(Definitions)
A typical way to disambiguate a concept from all others is to provide
a "definition" for it.$$ As Feigenbaum's EPAM studies showed, one can
never be sure that this definition will specify the concept uniquely
for all time. In the distant future, some new concept may differ in
ways thought to be ignorable at the present time. $ Almost every
concept had some entries initially supplied on its "Definitions"
facet. The format of this facet is a list of entries, each one
describing a separate definition. A single entry will have the
following parts:
.BN
λλ Descriptors: Recursive/Linear/Iterative, Quick/Slow,
Opaque/Transparent, Once-only/Early/Late, Destructive/Nondestructive.
λλ Relators: Reducing to the definition of concept X, Same as Y
except..., Specialized version of Z, Using the definition of W, etc.
λλ Predicate: A small, executable piece of LISP code, to tell if any
given item is an example of this concept.
.E
The predicate or "code" part of the entry must be faithfully described by the
Descriptors, must be related to other concepts just as the Relators
claim.
The predicate must be a LISP function which
take argument(s) and return either T or NIL (for
True/False), depending on whether or not the argument(s) can be
regarded as examples of the concept.
The argument "α{A Bα}" should
satisfy the predicate of any valid definition entry of the Sets
concept. This triple of arguments <{A B}, {A C}, {A B C}> should
satisfy any definition of the Set-union concept, since the third is
equal to the Set-union of the first two arguments.
Here is a typical entry from the Definitions facet of the Set-union concept:
.WBOX(11,11)
MBOX $
MBOX Descriptors: Slow, Recursive, Transparent $
MBOX $
MBOX Relators: Uses the algorithm for Set-insert, Uses the definition of Empty-set, $
MBOX Uses the definition of Set-equal, Uses the algorithm for Some-member, $
MBOX Uses the algorithm for Set-delete, Uses the definition of Set-union $
MBOX $
MBOX Code: λ (A B C) $
MBOX IF Empty-set.Defn(A) THEN Set-equal.Defn(B,C) ELSE $
MBOX X ← Some-member.Alg(A) $
MBOX A ← Set-delete.Alg(X,A) $
MBOX B ← Set-insert.Alg(X,B) $
MBOX Set-union.Defn(A,B,C) $
.SUPAGE: PAGE;
.EBOX
Let me stress that this is just one entry, from one facet of one
concept.
The notation "X ← Some-member.Alg(A)" means that any one algorithm
for the concept Some-member should be accessed, and then it should be
run on the argument A. The result, which will be an element of A, is
to be assigned the name "X". The effect is to bind the variable X to
some member of set A.
In the actual LISP implementation, the
ELSE part of the conditional is really coded$$
The expression "(f.Defn a1 a2...)" means "apply the predicate part of
a definition of f, to arguments a1, a2,...". This definition is to be
randomly selected from the entries on the Definitions facet of
concept f. $ as:
.B0
(Set-union.Defn (Set-delete.Alg (SETQ X (Some-member.Alg A)) A)
(Set-insert.Alg X B)
C
)
.E
This particular definition is not very efficient, but it is described
as Transparent. That means it is very well suited to analysis and
modification by AM itself. Suppose some heuristic rule wants to
generalize this definition. It can peer inside it, and, e.g., replace
the base step call on Set-equal, by a call on a generalization of
Set-equal (say "Same-length"$$ For disjoint sets, the new definition
would specify the operation which we call "addition". $).
How could ⊗4different⊗* definitions help here? Suppose there were a
definition which first checked to see if the three arguments were
Set-equal to each other, and if so then it instantly returned T as
the value of the definition predicate; otherwise, it recursed into
Set-union.Defn again. This might be a good algorithm to try at the
very beginning, but if the Equality test fails, we don't want to keep
recursing into this definition. This algorithm should thus have a
descriptor labelling it ONCE-ONLY EARLY.
A typical kind of entry for the Definitions facet of an operation is
to simply call on the ⊗4Algorithms⊗* part of that same concept. Here
is such an entry from the Definitions facet of the Set-union concept:
.WBOX(12,14)
MBOX Descriptors: none $
MBOX $
MBOX Relators: Uses the definition of Set-equal, Uses the algorithm for Set-union $
MBOX $
MBOX Code: λ (A B C) Set-equal.Defn(C, Set-union.Alg(A,B)) $
.EBOX
This definition is a trivial call on the "Algorithms" facet of
Set-union. That is, one way to test whether C is the set-union of A
and B, is simply to ⊗4run⊗* set-union on A and B, and compare the
result against C. The descriptors and relators of the particular
algorithm which is chosen will then be added to the descriptors and
relators which exist so far on this entry. Note that the box above
(like the box on the previous page) is simply one entry on the
Definitions facet of the Set-union concept.
There are three purposes to having descriptors and relators hanging
around:
.BN
λλ For the benefit of the user. AM appears more intelligent because
it can ⊗4describe⊗* the kind of definition it is using -- and why.
λλ For the sake of efficiency. When evaluating whether C really does
equal A∪B, AM wants the quickest definition. When trying to
generalize Set-union, AM needs a very transparent one. This way, it
won't waste its time with the wrong definition at the wrong time. If
there is an EARLY definition, it may get called on only at the
"proper" time.
λλ For the benefit of the heuristic rules. Often, a left- or a
right-hand-side will ask about a certain kind of definition. For
example, ⊗6"If a transparent definition of X exists, then try to
specialize X"⊗*.
.E
Granted that Descriptors and Relators are useful, how do these
"meta-level" modifiers get filled in, for newly-created$$ For
initially-supplied definition entries, the author hand-coded these
modifiers. $ concepts? All such powers are embedded in the fine
structure of the heuristic rules. This is true for the Algorithms
facet as well, and will be illustrated in the very next subsection.
Let me pull back the curtain a little further, and expose the actual
implementation of these ideas in AM. The secrets about to be
revealed will not be acknowledged anywhere else in this document.
They may, however, be of interest to future researchers. Each
concept may have a cluster of Definition facets, just as it can have
several kinds of Examples facets. These include three types:
Necessary and sufficient definitions, necessary definitions, and
sufficient definitions. These three types have the usual
mathematical meanings. All that has been alluded to before (and
after this subsection) is the necc&suff type of definition (x is an
example of C ⊗4if and only if⊗* x satisfies C.Def/necc&suff). Often,
however, there will be a much quicker sufficient definition (x
satisfies C.Def/suf, ⊗4only if⊗* x is certainly a C). Similarly,
entries on C.Def/nec are useful for quickly checking that x is
⊗4not⊗* an example of C (to check this, it suffices to verify that x
⊗4fails⊗* to satisfy a necessary definition of C).
So given the task of deciding whether or not x is an example of C, we
have many alternatives:
.BN
λλ If x is a concept, see if C is a member of x.ISA (if so, then x is
an example of C).
λλ If x is a concept, ripple to collect ISA's(x), and see if C is a
member of ISA's(x).
λλ If there is a fast sufficent definition of C, see if x satisfies
it.
λλ If there is a fast necessary definition of C, see if x fails it
(if so, then x is ⊗4not⊗* an example of C).
λλ If there is a necessary and sufficient definition of C, see whether
or not x satisfies that definition (this may show that x is or is not
an example of C).
λλ Recurse: check to see if x is an example of any specialization of
C.
λλ Recurse: check to see if x is ⊗4not⊗* an example of some
generalization of C (if so, then x is ⊗4not⊗* an example of C),
.E
In fact, there is a LISP function, IS-EXAMPLE, which performs those
steps in that order. At each moment, there is a timer set, so even
if there is a necessary and sufficient definition hanging around, it
might run out of time before settling the issue one way or the other.
Each time the function recurses, the timer is granted a smaller and
smaller quantum, until finally it has too little to bother recursing
anymore. There is a potential overlap of activity: to see if x is an
example of C, the function might ask whether x is or is not an
example of a particular generalization of C (step 7, above); to test
⊗4that⊗*, AM might get to step 6, and again ask if x is an example of
C. Even though the timer would eventually terminate this fiasco (and
even though the true answer might be found despite this wasted
effort) it is not overly smart of AM to fall into this loop.
Therefore, a stack is maintained, of all concepts which the
IS-EXAMPLE function tried to test on argument x. As the function
recurses, it adds the current value of C to that stack; this value
gets removed when the recursion terminates, when that recursive call
"returns" a value.
. SSSEC(Algorithms)
Earlier, we said that each concept can have any facets from the universal fixed set
of 25 facets.
This is not strictly true. Sometimes, a whole class
of concepts will possess a certain type of facet which no others may meaningfully
have. If C can have that facet, then so can any specialization of C.
Typically, there will be some concept C such that the examples of C are precisely the
set of concepts which can possess the new facet.
That is, there will be a ⊗4domain of applicability⊗* for the facet, just
as we defined such domains of applicability for heuristics.
For example, consider the "Domain/Range" facet. It is meaningful only to
"operations", but really ⊗4is⊗* an important feature of all operations.
Its domain of applicabilty is Operation.
The kinds of facets -- including all such limited "jargon" facets -- is fixed
once and for all. New kinds of facets cannot be conceived and added by AM itself.
If desired, one can view all this in a more general light.
For each facets f, the only concepts which
can have entries for facet f are examples of some particular concept J(f)
-- the "J" stands for "jargon".
J(f) is the domain of applicability of facet f.
If C is any concept which is not an example of J(f), then it can never
meaningfully possess any entries for that facet f.
For almost all facets f, J(f) is "Any-concept". Thus any concept can possess
almost any facet.
For example, J(Defn)="Any-concept", so any concept may have definitions.
There are a few more restricted facets. For example,
J(Domain/range)="Operation". So only operations can have domain/range facets.
The concept "Sets", which is not an operation, can't have a domain/range facet.
Similarly, J(Algorithms)="Actives". This facet is the subject of this section.
The Algorithms facet is present for all -- but only
for -- Actives
(predicates, relations, operations).
The representation is, as usual, a list of entries, each one
describing a separate algorithm. A single entry will have the following parts:
.BN TURN OFF "-"
λλ Descriptors: Recursive/Linear/Iterative, Quick/Slow, Opaque/Transparent,
Once-only/Early/Late,
Destructive/Nondestructive.
λλ Relators: Reducing to the algorithm for concept X,
Same as Y except...,
Specialized version of Z's algorithm, Using the algorithm for W, etc.
λλ Program: A small, executable piece of LISP code, for actually running C.
.E
.RECURPAGE: PAGE;
Note the similarity to the format for the Definitions facets of concepts.
Instead of a LISP predicate, however, the Algorithms facets possess a LISP function
(an executable piece of code whose value
will in general be other than True/False).
That "program" part of the entry must be
faithfully described
by the Descriptors, must be related to other concepts just as the
Relators claim, must take
arguments and return values as specified in the Domain/Range facet of C, and
when run on any arguments, the resultant
<args value> pair must satisfy the Definitions facet of C.
There is an extra level of sophistication which is available but rarely used in AM.
The descriptors can themselves be small numeric-valued functions. For example,
instead of just including the Descriptor "Quick",
and instead of just giving a fixed number for the speed of the algorithm,
there might be a little program there, which looked at the arguments fed to the
algorithm, and then estimated how fast this algorithm would be.
The main reason for not using this feature more heavily is that most of the
algorithms are fairly fast, and fairly constant in performance. It would be silly to spend
much time recomputing their efficiency each time they were called. If the
algorithm is recursive, this conjures up even sillier pictures.
The main reason in support of using this feature is of course "intelligence":
in the long run, processing a little bit before deciding which algorithm to run
⊗4has⊗* to be the winning solution. At the moment, it is not yet cost-effective.
Here is a typical entry from the Algorithms$$
note that it is similar to -- but not identical to -- the entry shown
on page {[3]SUPAGE}, of a ↓_Definition_↓ of Set-union. $
facet of the Set-union concept:
.WBOX(11,11)
MBOX $
MBOX Descriptors: Slow, Recursive, Transparent $
MBOX $
MBOX Relators: Uses the algorithm for Set-insert, Uses the definition of Empty-set, $
MBOX Uses the algorithm for Some-member, Uses the algorithm for Set-insert, $
MBOX Uses the algorithm for Set-union $
MBOX $
MBOX Code: λ (A B) $
MBOX IF Empty-set.Defn(A) THEN B ELSE $
MBOX X ← Some-member.Alg(A) $
MBOX A ← Set-delete.Alg(X,A) $
MBOX B ← Set-insert.Alg(X,B) $
MBOX Set-union.Alg(A,B) $
.EBOX
Note that the Descriptors don't say whether this algorithm is destructive$$
A LISP algorithm is destructive if it physically, permanently modifies the
list structures it is fed as arguments. Set-union(A,B) is destructive if
-- after running -- A and B don't have the same values they started with.
The advantages of destructive operations are increased speed,
decreased space used up,
fewer
assignment statements. The danger of course is in accidentally destroying some
information you didn't mean to. $
or not.
That means that this same algorithm can be used either destructively or not,
depending on what AM wants.
More precisely, it's up to the algorithms which get called on by this one.
If they are all
chosen to be destructive, so will Set-union. If they all copy their arguments first
then Set-union will ⊗4not⊗* be destructive.
For example, note how the algorithm calls on Set-insert(X,B). If this is destructive,
then at the end B will have been physically modified to contain X; the original
contents of B will be lost.
This particular algorithm is not very efficient, but it is described as Transparent.
That means it is very well suited to analysis and modification by AM itself.
Suppose
some heuristic rule
wants to specialize this algorithm. It can peer inside it, and,
e.g., replace the variable X in (Set-insert X B) by the constant "T".$$
This is a fairly useless new operation, of course. It adds T to B unless A is empty,
in which case this operation has no effect at all. $
Why should AM bother storing multiple algorithms for the same concept?
Consider this example again, of Set-union. Suppose there were an algorithm
which first checked to see if the two arguments were Equal to each other, and if so
then it instantly returned one of them as the final value for Set-union;
otherwise, it recursed into Set-union.Alg.
This might be a good algorithm to try
at the very beginning, but if the Equality test fails, we
don't want to keep recursing into this definition.
This algorithm should thus have a descriptor labelling it ONCE-ONLY EARLY.
Also, there is an iterative algorithm which checks to see if A
equals B,
and if so then it returns B. If not, the algorithm proceeds to check that A
is shorter than B,
and if not it switches them. Finally, it enters an iterative loop similar to the
recursive one above: it repeatedly transfers an element from A to B, using
Some-member, Set-delete and Set-insert. This iterative loop repeats until
A becomes empty.
While more efficient than the recursive one, this definition is less transparent.
An even more efficient algorithm is provided, but it is totally opaque:
.WBOX(18,18)
MBOX Descriptors: Quick, Non-recursive, Non-destructive, Opaque $
MBOX $
MBOX Relators: none $
MBOX $
MBOX Code: λ (A B) (UNION A B) $
.EBOX
This algorithm calls on the LISP function "UNION" to perform the set-union.
It is the "best" algorithm to choose unless space is critical, in which case a
destructive algorithm must be chosen, or unless AM wishes to inspect it rather
than run it, in which case a transparent one must be picked.
All the details about understanding the descriptors and relators are embedded in the
fine structure of the heuristic rules. A left-hand-side may test whether a
certain kind of algorithm exists for a given concept. A right-hand-side which
fills in a new algorithm must also worry about filling
in the appropriate descriptors
and relators. As with newly created concepts, such information is trivial to fill in
at the time of creation, but becomes much harder after the fact.
Here is a typical heuristic rule which results in a new entry being added to the
Algorithms facet of the newly-created concept named Compose-Set-Intersect&Set-Intersect:
.B816
.ONCE INDENT 4
IF the task is to Fillin Algorithms for F,
and F is an example of Composition
and F has a definition of the form F≡GoH,
and F has no transparent, nonrecursive algorithm,
.ONCE INDENT 4
THEN add a new entry to the Algorithms facet of F,
with Descriptors: Transparent, Non-recursive
with Relators: Reducing to G.Alg and H.Alg,
Using the Definition of <G.Domain>
with Program: λ (||<G.Domain>||,||<H.Domain>||-1,X)
.INDENT 30
(SETQ X (H.Alg ||<G.Domain>||))
(AND
.INDENT 33
(<G.Domain>.Defn X)
(G.Alg X ||<H.Domain>||-1))
.E
The intent of the little program which gets created
is to apply the first operator, check that the
result is in the domain of the second, and then apply the second operator.
The expression ||<G.Domain>|| means find a domain/range entry for G,
count how many domain components there are, and form a list that long
from randomly-chosen variable names (u,v,w,x,y,z).
For the case mentioned above, F = Compose-Set-Intersect&Set-Intersect,
G = Set-Intersect,
and H = Set-Intersect. The domain of
G is a pair of Sets, so
||<G.Domain>|| is a list
of 2 variables, say (u v). Similarly,
||<H.Domain>||-1 is a list
of 1 variable, say (w). Putting all this together, we see that
the new definition entry created for
Compose-Set-Intersect&Set-Intersect
would look like this:
.WBOX(15,15)
MBOX $
MBOX Descriptors: Non-Recursive, Transparent $
MBOX $
MBOX Relators: Reducing to Set-Insersect.Alg, Using the definition of Sets $
MBOX $
MBOX Code: λ (u,v,w,X) $
MBOX (SETQ X (Set-Intersect.Alg u v)) $
MBOX (AND $
MBOX (Sets.Defn X) $
MBOX (Set-Intersect.Alg X w) $
.EBOX
Let me make clear here one "kludge" of the AM program. At times, AM will
be capable of producing only a slow algorithm for some new concept C.
For example, TIMES-1-(x) was originally defined by AM as a blind, exhaustive search
for bags of numbers whose product is x. As AM uses that algorithm more and more,
AM records how slow it is. Eventually, a task is selected of the form
⊗6"Fillin new algorithms for C"⊗*, with the two reasons being that the existing
algorithms are all too slow, and they are used frequently.
At this point, AM should draw on a body of rules which take a declarative
definition and transform it into an efficient algorithm, or which take an
inefficient algorithm and speed it up. Doing a good job on just those rules
would be a mammoth undertaking, and the author decided to omit them.
Instead, the system will occasionally beg the user for a better (albeit
opaque) algorithm for some particular operation.
In general, the only requests were for inverse operations, and even then only
a few of them. The reader who wishes to know more about rules for creating
and improving LISP algorithms is directed to [Darlington and Burstall] and [ref].
. SSSEC(Domain/Range)
Another facet possessed only by active concepts is Domain/Range.
The syntax of this facet is quite simple. It is a list of entries, each of the form
⊗6< D↓1 D↓2... α→ R >⊗*, where there can be any number of D↓i's preceding the arrow,
and R and all the D↓i's are the names of concepts.
Semantically, this entry means that the active concept may be run on
a list of arguments
where the first one is an example of D↓1, the second an example of D↓2, etc.,
and in that case will return a value
guaranteed to be an example of R.
In other words, the concept may be considered a relation on the cross-product
D↓1xD↓2x...xR.
We shall say that the ⊗4domain⊗* of the concept is
D↓1xD↓2x..., and that its ⊗4range⊗* is R. Each D↓i is called a
⊗4component⊗* of the domain.
For example, here is what the Domain/Range facet of TIMES might look like:
.WBOX(18,25)
MBOX α{ $
MBOX < Numbers Numbers α→ Numbers > $
MBOX < Pos-Numbers Pos-Numbers α→ Pos-Numbers > $
MBOX < Neg-Numbers Neg-Numbers α→ Pos-Numbers > $
MBOX < Pos-Numbers Neg-Numbers α→ Neg-Numbers > $
MBOX < Perf-Squares Perf-Squares α→ Perf-Squares > $
MBOX < Bags-of-Numbers α→ Numbers > $
MBOX α} $
.EBOX
Here is what the Domain/Range facet of Set-Union might look like:
.WBOX(19,27)
MBOX α{ $
MBOX < Sets Sets α→ Sets > $
MBOX < Nonempty-sets Sets α→ Non-empty-sets > $
MBOX < Sets-of-Sets α→ Sets > $
MBOX α} $
.EBOX
The Domain/Range part is useful for pruning away absurd compositions, and
for syntactically suggesting compositions and "coalescings".
Let's see what this means.
Suppose some rule sometime tried to compose TIMES⊗7o⊗*Set-union.
A rule tacked onto Compose says to ensure that the range of Set-union
at least intersects
(and preferably is ⊗4equal⊗* to)
some component of the domain of TIMES. But there
are no entities which are both sets and numbers$$
Why? The number n, to AM, is represented in unary, as a bag of n T's.
None of these are sets.
The composition "TIMESoBAG-UNION" would have made sense to AM.
$; ergo this fails
almost instantaneously.
This is too bad, since there was probably a good reason (e.g., intuition)
for trying this composition. If the activation energy is high enough, AM
will continue trying to force it through.
The failure arose because Sets could not be viewed as if they were Numbers.
A relevant rule says:
.B816
IF you want to view X's as if they were Y's,
THEN seek an interesting operation F from X to Y, to do the viewing.
.E
So AM had to locate any and all operations whose domain/range had an
entry of the form <Setsα→Numbers>.
The only such operation known to AM at the time was F=Length.
So the composition produced was TIMES[X, Length(Set-union(Y,Z))].
Notice that if the composition Set-union⊗7o⊗*Set-union is proposed, there will be
no conflict, since the range of Set-union obviously intersects one component
of the domain of Set-union.
How can AM determine the domain/range of this composition? A rule tacked onto
Compose indicates that if F=G-o-H, and a domain/range entry for G is
<A...X...B α→ C>, and an entry for H is <D...E α→ Y>, and Y intersects X, then
an entry for F's domain/range is <A...D...E...B α→ C>. That is, the domain
of H is substituted for the single component of the domain of G which can be
shown to intersect the range of H.
Purely syntactically, AM can thus compute some domain/range entries for the
composition Set-union-o-Set-union.
.BEGIN FILL SELECT 6 PREFACE 0 INDENT 4,8,0
< Sets Sets α→ Sets> and < Sets Sets α→ Sets> combine to yield
< Sets Sets Sets α→ Sets >
< Non-empty-sets Sets α→ Non-empty-sets> and < Sets Sets α→ Sets> combine to yield
< Non-empty-sets Sets Sets α→ Non-empty-sets >
.E ONCE PREFACE 0
and so on. Similarly, one can compute an entry for the domain/range facet of the
previous composition of three operations TIMES-o-Length-o-Set-union:
.BEGIN FILL SELECT 6 PREFACE 0 INDENT 4,8,0
< Sets Sets α→ Sets>, < Sets α→ Numbers>, and < Numbers Numbers α→ Numbers >
combine to yield
< Numbers Sets Sets α→ Numbers >
.E
So when computing TIMES( X, Length( Set-union(Y,Z))), both Y and Z can be
sets, and X a number, and the result will be a number.
The claim was also made that Domain/Range facets help propose plausible coalescings.
By "⊗4coalescing⊗*" an operation,
we mean defining a new one, which differs from the original one in that
a couple of the arguments must now coincide. For example,
coalescing TIMES(x,y), we get the new operation F(x) defined as TIMES(x,x).
Syntactically, we can coalesce a pair of domain components of the domain/range
facet of an operation if those two domain components are equal, or if
one of them is a specialization of the other, or even if they merely intersect.
In the case of one related to the other by specialization, the more specialized
concept will replace both of them, In case of merely intersecting, an extra test
will have to be inserted into the definition of the new coalesced operation.
Given this domain/range entry for Set-insert: < Anything Sets α→ Sets >, we see that
it is ripe for coalescing. Since Sets is a specialization of Anything, the new
operation F(x), which is defined as Set-insert(x,x), will have a domain/range
entry of the form < Sets α→ Sets >. That is, the specialized concept Sets
will replace both of the old domain elements (Anything and Sets).
F(x) takes a set x and inserts it into itself. Thus F({a,b})={a,b,{a,b}}.
In fact, this new operation F is very exciting because it always seems to give
a new, larger set than the one you feed in as the argument.
We have seen how the Domain/range facets can
prune away meaningless coalescings, as well as meaningless
compositions. Any proposed composition or coalescing will at least be syntactically
meaningful. If all compositions are proposed only for at least one good
semantic reason, then those passing the domain/range test, and hence
those which ultimately get created, will all be valuable new concepts.
Since almost all coalescings are semantically interesting, ⊗4any⊗* of them which
have a valid Domain/Range entry will get created and probably will be interesting.
This facet is occasionally used to suggest conjectures to investigate. For example,
a heuristic rule says that if the domain/range entries have the form
<D D D... → genl(D) >, then it's worthwhile seeing whether the value of this
operation doesn't really always lie inside D itself. This is used right after the
Bags↔Numbers analogy is found, in the following way. One of the Bag-operations
known already is Bag-union. The analogy causes AM to consider a new operation,
with the same algorithm as Bag-union, but restricted to Bags-of-T's
(numbers in unary
representation). The Domain/range facet
of this new, restricted mutation of Bag-union
contains only this entry:
<Bags-of-T's Bags-of-T's → Bags>. Since Bags is a generalization of Bags-of-T's, the
heuristic mentioned above triggers,
and AM sees whether or not the union of two Bags-of-T's is
always a bag containing only T's. It appears to be so, even in extreme cases, so the
old Domain/range entry is replaced by this new one:
<Bags-of-T's Bags-of-T's → Bags-of-T's>.
When the user asks AM to call these bags-of-T's "numbers", this entry becomes
<Numbers Numbers → Numbers>.
In modern terms, then, the conjecture suggested was that the sum of two numbers
is always a number.
To sum up this last ability in fancy language,
we might say that
one mechanism for proposing
conjectures is the prejudicial belief in the unlikelihood of asymmetry.
In this, case, it is asymmetry in the parts of a Domain/range entry that
draws attention.
Such conjecturing can be done by any action part of any heuristic rule;
the Conjec facet entries don't have a monopoly on initiating this type of activity.
. SSSEC(Worth)
How can we represent the worth of each concept? Here are some
possible suggestions:
.BN
λλ The most intelligent solution is "purely symbolically". That is, an
individualized description of the good and bad points of the concept;
when it is useful, when misleading, etc.
λλ A simpler solution would be to "standardize" the above symbolic
description once and for all, fixing a universal list of questions. So each
concept would have to answer the questions on this list (How good are
you at motivating new concepts?, How costly is your definition to
execute?,...). The answers might each be symbolic; e.g., arbitrary
English phrases.
λλ To simplify this scheme even more, we can assume that the answers
to each question will be numeric-valued functions (i.e, LISP code
which can be evaluated to yield a number between 0 and 1000). The
vector of numbers produced by Evaluating all these functions will
then be easy to manipulate (e.g. using dot-product, vector-product,
vector-addition, etc.), and the functions themselves may be inspected
for semantic content. Nevertheless, much content is lost in passing
from symbolic phrases to small LISP functions.
λλ A slight simplification of the above would be to just store the
vector of numbers answering the fixed set of questions; i.e., don't
bother storing a bunch of programs which compute them dynamically.
λλ Even simpler would be to try to assign a single "worthwhileness"
number to each concept, in lieu of the vector of numbers.
Simple arithmetic operations could manipulate Worth values then.
In some
cases, this linear ordering seems reasonable ("primes" really are
better than "palindromes".) Yet in many cases we find concepts which
are too different to be so easily compared (e.g., "numbers" and
"angles".)
λλ The least intelligent solution is none at all: each concept is
considered equally worthwhile as any other concept. This threatens
to be combinatorial dynamite.
.E
As we progress along the intelligent→→→trivial dimension, we find
that the schemes get easier and easier to code, the Worth values get
easier and easier to deal with, but the amount of reliable knowledge
packed into them decreases.
The third scheme was initally chosen for AM: a vector of numeric
answers to a fixed set of questions.
Here are those questions, the components of the Worth vectors for each concept:
.BN
λλ Overall aesthetic worth.
λλ Overall utility. Combination of usefulness, ubiquity.
λλ Age. How many cycles since this concept was created?
λλ Life-span. Can this concept be forgotten yet?
λλ Cost. How much cpu time has been spent on this concept, since its
creation?
.E
Notice that in general no constant number can answer one of these questions
once and for all (consider, e.g., Life-span). Each answer will have to be
something like a numeric-valued LISP
function.
A few questions which crop up often are not present on this list,
since they can be answered trivially using standard LISP functions
(e.g., "How much space does concept C use up?" can be found by
calling the function "COUNT" on the property-list of the LISP atom
"C").
Another kind of question, which was anticipated and did in fact come
up frequently, is of the form "How good are the entries on facet F of
this concept?", for various values of F. Since there are a couple
dozen kinds of facets, this would mean adding a couple dozen more
questions to the list. The line must be drawn somewhere. If too much
of AM's time is drained by evaluating where it is already, it'll
never progress.
The heuristic rules are responsible for initially setting up the
various entries on the Worth facets of new concepts, and for
periodically altering those entries for ⊗4all⊗* concepts, and for
delving into those entries when required.
.ONCE TURN ON "{}"
Recent experiments have shown (see page {[3] EX3PAGE}) there was little
change in behavior when each vector of functions was replaced by a
single numeric function (actually, the sum of the values of the
components of the "old" vector of functions); there wasn't even too
much when this was replaced by a single number. There ⊗4was⊗* a
noticable degradation (but no collapse) when all the concepts'
numbers were set equal to each other initially.
For the purposes of this document, then (except for this page and the
discussion of Experiment 3), we may as well assume that each concept
has a single number (between 0 and 1000) attached as its overall
"Worth" rating. This number is set and referenced and updated by
heuristic rules. Experiment 3 can be considered as showing that a
more sophisticated Worth scheme is not necessary for the particular
kinds of behaviors that AM exhibits.
. SSSEC(Interest)
Now that we know how
how to judge the overall worth of the concept
"Composition", let's turn to the question of
how interesting some specific composition is? Unfortunately, the Worth
facet really has nothing to say about that problem.
The Worth of the concept "Operation" has little effect on how interesting
a particular operation is: "Add" is very interesting, and
"Constant-o-Constant" is less so.
The Worth facets of ⊗4those⊗* concepts will say something about their overall value.
And yet there is some knowledge, some "features" which would make any composition
more interesting:
.BN
Are the domain and range of the composition equal to each other?
Are interesting properties of each component of the composition preserved?
Are undesirable properties lost (i.e., ⊗4not⊗* true about the composition)?
Is the new composition equivalent to some already-known operation?
.E
These hints on "features to look for" belong tacked onto the Composition concept,
since they modify all compositions. Where and how can this be done?
For this purpose each concept -- including "Compositon" --
can have entries on its "⊗4Interest⊗*" facet.
It contains a bunch of features which
(if true) would make any particular example of the current concept interesting.
The format for the Interest facet is as follows:
.BEGIN NOFILL INDENT 4 PREFACE 0 SELECT 6
< Conflict-matrix
<Feature1, Value1, Reason1, Used1>
<Feature2, Value2, Reason2, Used2>
⊗8###⊗*
<FeatureK, ValueK, ReasonK, UsedK>
.ONCE INDENT 42
>
.E
This is the format of the facet itself, not of each entry. The
conflict-matrix is special and will be discussed below. Each
Feature/Value/Reason/Used qudruple will be termed an "entry" on the
Interest facet.
Each "Feature" is a LISP predicate, indicating whether or not some
interesting property is satisfied. The corresponding "Value" is a
numeric function for computing just how valuable this feature is.
The "Reason" is a token (usually an English phrase) which is tacked
along and moved around, and can be inspected by the user. The "Used"
subpart is a list of all the concepts whose definitions are known to
incorporate$$ Not ↓_SATISFY_↓ the feature. Thus the general concept
Domain=Range-op ↓_incorporates_↓ the feature "range(x)is one component of
domain(x)" as just
one of the conjuncts in its definition. On the other hand, Set-union satisfies
the feature, since its range, Sets, relly is one componentof its domain. $
this feature; all examples of such concepts will then automatically satisfy this
Feature.
.GROUP
For example, here is one entry from the Interest facet of Compose:
.B816
FEATURE: Domain(Arg1)=Range(Arg2)
VALUE: .4 + .4xWorth(Domain(Arg1)) + .2xPriority(current task)
REASON: "The composition of Arg1 and Arg2 will map from a set back
into that same set"
USED: Compose-with-self-Domain=Range-operation, Interesting-compose-4
.E
.APART
Just as with Isa's and Generalizations, we can make a general
statement about Interest features:
.ONCE PREFACE 1 INDENT 6
⊗6Any feature tacked onto the Interest facet of any member of ISA's(C),
also applies to C.⊗*
.ONCE PREFACE 1
That is, X.Interest is relevant to C iff C is an example of X.
For example, any feature which makes an operation interesting, also
makes a composition interesting.
So we'd like to define the function
Interests(C) as the union of the Interest features found tacked onto
any member of ISA's(C).$$ Recall that the formula for
this is ISA's(C) = Generalizations(Isa(Generalizations(C))). $
But
some of these might have already been conjoined to a definition, to
form the concept C (or a generalization of C). So all C's will
trivially (by definition) satisfy such features. The USED subparts
can be employed to find such features. In fact, the final value of
Interests(C) is the one computed above,
using ISA's(C),
but after eliminating all the
features whose USED subparts pointed to any member of
ISA's(C).
This covers the purpose of each subpart of each entry on a typical
Interest facet. Now we're ready to motivate the presence of the
Conflict-matrices.
Often, AM will specialize a concept by conjoining onto its definition
some features which would make any example of the concept
interesting. So ⊗4any⊗* example of this new specialized concept is
thus guaranteed to be an ⊗4interesting⊗* example of the old concept.
Sometimes, however, a pair of features are exclusive: both of them
can never be satisfied simultaneously. For example, a composition
can also be interesting if "arg2" is an operation from Range(arg1)
into a set which is much more interesting than either Domain(arg1) or
Range(arg1). Clearly, this feature and the one shown above can't
both be true
(if x=y, then x can't be much more interesting than y, can it?).
If AM doesn't realize this, however, it might create a
new concept, called Interesting-composition, defined as "any
composition satisfying both of those features". But then this concept
will be vacuous: ⊗4no⊗* operation
can possibly satisfy that over-constrained
definition; this new concept will have no examples; it is the
null concept; it is trivially forgettable. Merely to think
of it is a blot on AM's claim to rationality.
The "Conflict-matrix" is specified to prevent many such trivial
combinations from eating up a lot of AM's time (and, as usual, it helps to
make AM appear smarter). If there are K features present for the
Interest facet of the concept, then its conflict-matrix will be a KxK
matrix. In row i, column j of this matrix is a letter, indicating the
relationship between features i and j:
.GROUP
.BN
E Exclusive of each other: they both can't be true at the same time.
→ Implies: If feature i holds, then feature j must hold.
← Implied
by: If feature j holds, then so does feature i.
= Equal. Feature i
holds precisely when feature j holds.
U Unrelated. As far as known,
there is no connection between them.
.E
.APART GROUP
These little relations are utilized by some of the heuristic rules.
Here is one such rule. Its purpose is to create a new, specialized
form of concept C, if many examples of C were previously found very
quickly.
.B816 ONCE INDENT 4
IF Current-task is (Fillin Specializations of C)
and ||C.Examples||>30
and Time-spent-on-C-so-far < 3 cpu seconds,
and Interests(C) is not null,
.ONCE INDENT 4
THEN create a new concept named Interesting-C,
Defined as the conjunction of C.Defn and the highest-valued member of
Interests(C) which is U (unrelated) to any feature USED in the definition of C.
and add the following task to the agenda: Fillin examples of
Interesting-C, with value computed as the Value subpart of the chosen
feature, for this reason: "Any example of Interesting-C is
automatically an interesting example of C".
and add "Interesting-C" to the USED subpart of the entry where that
feature was originally plucked from.
.E
.APART
.ONCE TURN ON "{}"
Of course, the LISP form of the
above rule is really more detailed about what to do,
but the general flavor of the interaction with the Interest facet
should come across. As before, the value desired is not C.Interest,
but rather the post-rippling value Interests(C). The quantity
Time-spent-on-C-so-far is one component of the Worth facet of C; it
might just as well have been accessed from some "Past-history" record
of AM's activities. The numbers in the rule -- and every little bit
of that rule -- were specified ad hoc by the author. This is true for
each rule initially present in AM. As Section
{[2]EXPT}.{[2]EXPTSSEC}
will discuss, the
precise numbers don't drastically affect the system's performance.
. SSSEC(Suggest)
This section describes a space-saving "trick", and a "fix-up" to undo
some potentially serious side-effects of that trick.
Readers
not interested in this level of detail may skip to the next subsection.
AM maintains a long list of tasks (the agenda), ordered by a global priority
rating scheme. Besides this, AM maintatins two threshholds: Do-threshhold and
a lower one, Be-threshhold.
When a new task is proposed, if its global priority is below Be-threshhold,
then it won't even be entered on the agenda. This value is set so low that
any task having even one mediocre reason will make it onto the agenda.
After a task is finished executing, the top-rated one from the agenda is selected
to work on next. If its priority rating is below Do-threshhold, however,
it is put back on the agenda, and AM complains that no task on the agenda is
very interesting at the moment. AM then spends a minute or so looking around for
new tasks, re-evaluating the priorities of the tasks on the agenda already, etc.
One way to find new tasks (and new reasons for already-exisiting tasks) is to
evaluate the "⊗4Suggest⊗*" facets of all the concepts in the system. More precisely,
the Suggest facet of a concept C consists of a list of LISP functions.
Each function accepts a number N as argument (representing some minimum value tolerable
for a new task), and the function returns as its value a list of new tasks.
These are then merged into the agenda, if desired.
Semantically, the functions contain heuristic rules for suggesting new
tasks. For example, here is one entry from the Suggest facet of Any-concept:
.B816 INDENT 4
IF there are no examples for concept C filled in so far,
THEN consider the task "Fillin examples of C", for the following reason:
"No examples of C filled in so far", whose value is half of Worth(C).
If that value is below arg1, then forget it; otherwise, try to add to to the
agenda.
.E
The argument "arg1" is that low numeric value, N, supplied to the Suggest facet.
This entry alone will produce a multitude of potential tasks;
for concepts whose Worth numbers
are high, or for which a task is already on the agenda to fill in their examples,
these suggested tasks will be remembered; most of the other ones will typically
be forgotten.
One use of
this facet is thus to "beef up" the agenda
whenever AM is discontented with all the tasks thereon. Afterwards, the
highest-ranking task will hopefully have a higher value than any did before.
Also, the two threshholds are reduced whenever this discontent ooccurs.
Both threshholds are raised slightly every time AM succeeds in picking and
executing a task. So they follow a pattern of slow increase, followed by a
sudden decrement, followed by another slow increase, etc.
This was intended to mimic a human's increasing expectations as he makes
progress.$$
This was based on personal introspection, and should be tested experimentally.
$ It also mimics the way a human strains his mind when an
obstacle to that progress appears; if the straining doesn't produce a brilliant
new insight, he grudgingly is willing
to reduce those expectations, and perhaps resume some "old path" abandoned earlier.
Another use of this facet is to re-suggest tasks that might have been dropped
from (or never made it onto) the agenda, because they weren't valued above
Be-threshhold. At the moment, that threshhold's
value might be much lower than it was,
and thus a fairly boring task will "stick". The Suggest facets can reproduce
most of the common tasks, and try to stick them on the agenda (albeit for a mediocre
reason). It will still usually require another reason for such a task to rise
to the very top of the agenda, and be selected and executed.
<< Pick better names for do- and be- threshholds? >
So the use of the two threshholds is really an unaesthetic space-saving device,
and the role of the Suggest facets is merely to correct the errors introduced in
this way. Since there is no convincing intuitive reason for having these facets
at all in a "just" world, they will not be mentioned much in the sequel.
. SSSEC(Fillin/Check)
There is one more level of structure to AM's representation of a concept than
has been revealed so far.
Each concept consists of a bunch of facets; each
facet follows the format layed down for it (and described in the
preceding several subsections).
Yet each facet of each concept can have two additional "subfacets"
(little slots that are hung onto any desired slot) named ⊗4Fillin⊗* and
⊗4Check⊗*.
The "Fillin" field of facet F of concept C is abbreviated
C.F.Fillin. The format of that subfield is a list of
heuristic rules. Semantically, each rule in C.F.Fillin should be relevant to
filling in entries for facet F of any concept on the list Examples(C).
This substructure is an implementation answer to the question of where to place
certain heuristic rules.
As an illustration, let me describe a typical rule which is found on
Compose.Examples.Fillin.
According to the last paragraph, this must be useful for filling in
examples of examples of compositions.
The rule says that if the composition A-o-B is
formed from two very time-consuming operations A and B, then it's worth
trying to find some examples of A-o-B by symbolic means; in this case,
scan the examples of A and of B, for some pair of examples
x→y (example of B) and y→z (example of A). Then posit that
x→z is an example of A-o-B.
This rule applies precisely to the task of filling in examples of
Examples(Composition).
Thus, it is relevant to the task "Fill in examples of Insert-o-Insert".
It is irrelevant if you change "fillin" to "check", or if you change the facet
(e.g., "Fill in ↓_⊗4algorithms⊗*_↓ for Insert-o-Insert"),
or the class of concept
(e.g., "Fill in examples of ⊗4↓_Set-union_↓⊗*)$$ Note
that it does make sense if you replace the concept "Insert o Insert"
by any other example of a Composition (e.g., "Fill in examples of
Set-Union o Set-intersection").
$.
As another illustration, let me describe a typical rule which is found on
Compose.Conjec.Fillin. It
says that one potential conjecture about a given
composition A-o-B is that it is unchanged from A (or from B). This happens
often enough that it's worth examining each time a new composition is made.
This rule applies precisely to the task of filling in conjectures about particular
compositions.
The subfacet Any-Concept.Examples.Fillin is quite large; it contains all the known
methods for filling in examples of C (when all we know is that C is a concept).
Here are a few of those techniques:
.BN
λλ Instantiate C.Defn
λλ Search the
examples facets of all the concepts on Generalizations(C) for examples of C
λλ Run some of the concepts named in In-ran-of(C) [i.e., operations whose range
is C] and collect the resultant values.
.E
Any-Concept.Examples.Check is large for similar reasons.
A typical entry there says to examine each verified example of C: if
it is also an example of a specialization of C, then it must be removed
from C.Examples and inserted$$ Conditionally. Since each concept is of finite
worth, it is allotted a finite amount of space. A random number is generated to
decide whether or not to actually insert this example into the examples facet of
the specialization of C. The more that specialized concept is "exceeding its quota",
the narrower the range that the random number must fall into to have that
new item inserted. The probability is never precisely 1 or 0. $
into the Examples facet of that specialized concept.
Here is one typical entry from Operation.Domain/Range.Check:
.B816 ONCE INDENT 4
IF a domain/range entry has the form (D D D... → R),
and all the D's are equal, and R is a generalization of D,
.ONCE INDENT 4
THEN it's worth seeing whether (D D D... → D)
is consistent with all known examples of the operation.
If there are no known examples,
add a task to the agenda requesting they be filled in.
If there are examples, and (D D D... → D) is consistent, add it to the Domain/range
facet of this operation.
If there are some contradicting examples, create a new concept which is defined as
this operation restricted to (D D D... → D).
.E
Note that this "Checking" rule doesn't just passively check the designated facet; it
actively "fixes up" faulty entries, adds new tasks, creates new concepts, etc.
All the check rules are very agressive in this way.
For example, one entry on No-multiple-elements-structure.Examples.Check
will actually remove any multiple occurrences of an element from a structure.
As you might expect, the set Checks(C.F) of all relevant rules for
checking facet F of concept C is obtained as
(ISA's(C)).F.Check. That is, look for the Check subfacet of the
F facet of all the concepts on ISA's(C)).
Similarly, Fillins(C.F) is the union of the Fillin subfacets of the F facets of
all the concepts on ISA's(C).
When AM chooses a task like "Fillin examples of Primes", its first action is to
compute Fillins(Primes.Exs).
It does this by asking for ISA's(Primes); that is, a list of all concepts of which
Primes is an example. This list is: <Objects Any-concept Anything>.
So the relevant heuristics are gathered from Objects.Exs.Fillin, etc.
This list of heuristics is then executed, in order
(last executed are the heuristics attached to Anything.Exs.Fillin).
This subsection should explain what is meant when a concept's facet is
listed in the following format:
.WBOX(26,26)
MBOX ⊗8#⊗* $
MBOX ⊗8#⊗* $
MBOX Algorithms A1 A2 $
MBOX Examples E1 E2 E3 E4 E5 E6 $
MBOX Fillin Rule1 Rule2 $
MBOX Check Rule3 Rule4 Rule5 $
MBOX Domain/range DR1 DR2 DR3 $
MBOX Check Rule6 $
MBOX Conjecs C1 C2 C3 C4 C5 C6 $
MBOX Fillin Rule7 Rule8 $
MBOX Check Rule9 Rule10 $
MBOX ⊗8#⊗* $
MBOX ⊗8#⊗* $
.EBOX
.ONCE TURN ON "{}"
E.g., the entry Rule9 is a heuristic rule which may help to check
entries on the Conjecs facet of any example of this concept.
This notation will be used
in the remainder of the thesis (where a few scattered concepts are pictured), and
throughout Appendix {[2] ALLCON} (where all the
concepts are listed alphabetically).
. SSSEC(Other Facets which were Considered)
<< It's unclear whether or not this should go in the RESULTS sec. >
Most facets (like "Definitions") were anticipated from the very beginning
planning of AM, and proved just as useful as expected. Others (like "Intuitions")
were also expected to be very important, yet were a serious disappointment.
Still others (like "Suggest") were unplanned and grumblingly acknowledged as
necessary for the particular LISP program that bears the name AM.
Finally, we turn to a few facets which were initially planned, and yet which
were adjudged useless around the time that AM was coded. They were therefore
never really a part of the LISP program AM, although they figured in its
proposal. Let me list them, and explain why each one was dropped.
.BEGIN BNN←0; INDENT 0,3,0
λλ UN-INTERESTINGNESS. This was to be similar to the Interest part. It would
contain entries of the form feature/value/reason, where the feature would be
a ⊗4bad⊗* (dull, trivializing, undesirable, uninteresting) property that an
entity (a concept or a task) might possess.
If it did, then the value component would return a
negative number as its contribution to the worth/priority of that entity.
This sounded plausible, but turned out to be useless in practice:
(i) There were very few features one could point to which explicitly indicated
when something was boring; (ii) Often, a conjunction of many such features
would make the entity seem unusual, hence interesting; (iii) Most entities
were viewed as very mediocre unless/until specific reasons to the contrary,
and in those cases the presence a few boring properties would be outshadowed
by the few non-boring ones. In a sea of mediocrity, there is little need to
separate the boring from the very boring.
λλ JUSTIFICATION.
For conjectures (the awkward ones on Conjecs, the entries on Genl/Exs, etc.)
which were not absolutely certain, this part would contain the information
about why they were believed. In case the user (or another concept) wanted to
know, this would hopefully be convincing. In cases of contradictions arising
somehow, this facet was to keep hold of the threads that could be untangled
to resolve those paradoxes. As described earlier, this duty could naturally be
assumed by the Conjecs facet of each concept. The other intended role for this
facet was to hold sketches of the proofs of theorems.
Unfortunately, the intended concepts for Proof and Absolute truth were
never implemented, and thus most of the heuristic rules which would have interacted
with this facet are absent from AM. It simply was never needed.
λλ RECOGNITION
λOriginally, it was assumed that the location of relevant concepts and
their heuristics would be much more like a
free-for-all (pandemonium) than an orderly rippling process.
As with the original use of BEINGs$$ Interacting knowledge modules, each module
simulating a different expert at a round-table meeting. See [Lenat]. $, the
expectation was that each concept would have to "shout out" its relevance whenever
the activities triggered some recognition predicate inside that concept.
Such predicates were to be stored in this facet.
But it quickly became apparent that the triggering predicates which were the
left-hand-sides of the heuristic rules were quick enough to obviate the need
for pre-processing them too heavily. Also, the only rules relevant to a given
activity on concept C always seemed to be attainable by rippling in a certain
direction away from C. This varied with the activity, and a relatively small table
could be written, to specify which direction to ripple in (for any given desired
activity). We see that for "Fill-in examples of...", the direction to ripple in
is "Generalizations", to locate relevant heuristic rules.
For "Judge interest of..." the direction is also generalizations. For
"Access specializations of", the direction is Specializations, etc.
The only important point here is that the Recognition facet was no longer needed.
.E
.SSEC(AM's Starting Knowledge)
.CDIAG: PAGE;
.ONCE TURN ON "{}"
The first subsection presents a diagram of all the concepts AM started with,
with the lines indicating the
Generalizations/Specializations kinds of relationships.
The examples/isa's of those concepts are not diagrammed, but are
described in Section {SECNUM}.{SSECNUM}.2.
That subsection also describes each concept which ⊗4is⊗* diagrammed.
A fuller description of the concepts is provided in Appendix
{[2] ALLCON}. The third and last subsection of this section
discusses the choice of starting concepts.
. SSSEC(Diagram of Initial Concepts)
The diagram below represents the "topmost" concepts, connected via
Specialization links.
.B0
Anything
/ \
/ \
/ \
Any-concept ⊗4non-concepts⊗*
/ \
/ \
/ \
/ \
Activity Object
/ \ / ~ \
/ \ / ~ \
Predicate Operation Atom Conjec Structure
/ \ ~ / ~ ~ ~\
Constant-pred Equality-pred Truth-value / ~ ~ ~ \
/ ~ Empty~ \
/ ~ ~ \
Multiple-elements-allowed Non-mult Ord Unordered
\ \ \ \ / ~ / /
\ \ \ Osets ~/ /
\ \ \ / /
\ \ \ /~ /
\ \ Sets ~ /
\ \ ~ /
\ \ ∪ /
\ \ ∩ /
\ \ ∪ /
\ Lists /
\ \ /
\ \ /
\ ∃
\ / \
Bags \
Ord-pairs
.E
The concepts not diagrammed are ⊗4examples⊗* of the ones which are shown.
For example,
the two examples of Truth-value are True and False.
The concept "Operation" has several specializations and examples which
will be described in the next subsection.
Finally, we should note that many entities exist in the system
which are not themselves concepts. For example, the number "3", though it
be an ⊗4example⊗* of many concepts, is not itself a concept.
All entities which ⊗4are⊗* concepts are present on the list called
CONCEPTS, and they all have property lists (with facet names as the
properties). In hindsight, this somewhat arbitrary scheme is regrettable.
A more aesthetic designer might have come up with a more uniform system
of representation than AM's.
. SSSEC(Summary of Initial Concepts)
.ONCE TURN ON "{}"
Since the precise set of concepts is not central to the design and
quality of behaviors of AM, they are not worth detailing here.
On the other hand, a cursory familiarity with their names and definitions
should aid the reader in following the detailed material in future chapters.
For that reason, the
concepts will now be briefly described. The ordering is meant to
group together concepts which are semantically related, by starting at the
top of the diagram and meandering downward.
A fuller description of the concepts is provided in Appendix
{[2] ALLCON}. There the concepts are arranged alphabetically,
The reader is encouraged to consider that appendix as a dictionary.
ANYTHING and ANY-CONCEPT are self-explanatory. They are useful because they
hold all the very general tactics for filling in and checking each facet.
The definition of Anything is ⊗6"λ (x) T"⊗*; i.e., a predicate which will ⊗4always⊗*
return true. The definition of Any-concept is ⊗6"λ (x) xεCONCEPTS"⊗*.
CONCEPTS is AM's global list
of entities known to be concepts. Initially, this list contains the hundred or so
concepts which AM starts with (including those diagrammed on the preceding page).
Notice that the singleton {a} is an example of
Anything, but (since it's not on the list CONCEPTS)
it is not an example of Any-concept.
ACTIVITY represents something that can be "performed". All activities have
Domain/range facets, Algorithms facets, etc., and they are the ⊗4only⊗* concepts
which do have such facets.
OBJECTs, on the other hand, are static. They are like the subjects and
direct objects in sentences, while the Activities are like the verbs$$
As in English, a particular Activity can sometimes itself be the subject. $.
Activities are classified into two categories: PREDICATEs and OPERATIONs.
A predicate examines its arguments and returns either True or False. An operation
examines ⊗4its⊗* arguments and returns any number of values$$ An
operation which always returns precisely 1 value is what we usually call a
"function". $.
Assuming that the arguments lay in the domain
(as specified by some entry on its Domain/range facet),
then any value the operation returns
must lie within its range (as specified by that same Domain/range entry).
It is only due to the capriciousness of AM's initial design that
predicates are kept
distinct from operations.
Of course, each example of an operation can be viewed as if it were
a predicate; if F:A→B is any operation from A to B, then we
can consider F a relation on AxB, that is a subset of AxB,
and from there pass to viewing F as a (characteristic) predicate F:AxB→α{T,Fα}.
This is precisely what the Definitions facet of an operation
does.
Similarly, any predicate on Ax...xBxC
may be considered an operation (a multi-valued, not-always-defined function)
from Ax...xB into C.
There are no unary predicates. If there were one, say P:A→{T,F}, then that
predicate would essentially be a new way to view a certain subset of A;
the predicate would then be transformed into {a⊗6ε⊗*A|P(a)}, made into a new
concept, tagged as a specializaiion of A, and its definition would be
"λ(a) [A.Defn(a) ∧ P(a)".
The concept of RELATION was also initially present,
as a third kind of specialization of Active,
but this turned out not
to be useful very often. A relation was a set of ordered pairs, and AM could
switch from one view of an Active to another quite easily.
CONJEC is a concept which knows about -- and can store -- conjectures.
The only ones stored thereon are very flimsy ones, awaiting further tests.
ATOM is meant to represent an indivisible item: the name of something,
"True" (the LISP atom "T") and "False" (the atom "NIL").
By way of contrast, STRUCTURE is inherently divisible. A structure is
something that has members, that can be broken into pieces.
There are two questions one can ask about any kind of structure:
Is it ordered or not? Can there be multiple occurrences of the same element in
it or not? There are four sets of answers to these two questions, and each of the
four specifies a well-known kind of structure. SETS are structures which are
unordered and have no repeated elements. LISTS are diametrically opposite: they
are ordered and may have multiple elements.
BAGS are unordered and may have multiple elements; they are sometimes called
"multisets". For completeness AM started with the concept of OSETS (for ordered
sets), which disallowed multiple elements, but recognized the orderof elements
as significant. The Short-term-memory of Newell's production system PSG is an
example of an OSET, as is the line at the cafeteria (if you lose your place, it
matters, and there are never two of you in line at the same time).
Nevertheless, no real use was ever found for this kind of structure.
One could view a list as an "ordered bag" in an analogous fashion.
ORDERED-PAIR is a special kind of list, namely it always has length "2".
The only other specialized kind of structure that AM initially knows about is
EMPTY (and Nonempty). This means, a structure which does not have any elements.
COMPOSITION involves taking two operations A and B, and applying them in
sequence: A-o-B(x)⊗6≡⊗*A(B(x)).
This concept deals with (i) the activity of creating
new compositions, given a pair of operations; (ii) all the operations which were
created in this fashion. That is why this concept is both a specializiation of
and an example of Operation.
The same duality$$ Both a specialization of Operation and an
example of Operation. $ applies to
COALESCE. This very useful operation takes as its argument any operation
F(a,b,c,d...),
locates two domain components which intersect (preferably, which are equal;
say the second and third), and then creates a new operation G defined as
G(a,b,d...)⊗6≡⊗*F(a,b,b,d...). That is, F is called upon with a pair of arguments
equal to each other. If F were Times, then G would be Squaring.
If F were Set-insert, then
G would be the operation of inserting a set S into itself.
.ONCE TURN OFF "-"
Similar duality applies to the concept INVERTED-OP, which can invert an operation,
and also deal with any inverted operation. If F:X→Y is an operation, then
its inverse will be abbreviated F-1- (or INV-F), and F-1-(y) is defined as
all the x's in X for which F(x)=y. The domain and range of F-1- are thus the
range and domain of F.$$ Incidentally, if F-1- turns out to be a function (wherever
it was defined), then
we would say that F was 1-1 or "injective". $
The last concept which is both an example of and a specialization of Operation is
CANONIZE. This operation takes two predicates P1 and P2,
both defined over some domain AxA,
where P1 is a generalization
of P2. Canonize then tries to produce a
"standard representation" for elements of A, in the
following way. It creates an operation f from A into A, satisfying:
⊗6P1(x,y) iff P2(f(x),f(y))⊗*. Then any item of the form f(x) is called a canonical
member of A. The set of such canonical-A's is worth naming, and
it is worth investigating the restrictions of various operations' domains and ranges
to this set of canonical-A's$$ i.e., take an operation which used to have "A" as
one of its domain components or as its range, and try to create a new operation
with essentially the same definition but whose domain/range say "Canonical-A"
instead of "A". $.
"Canonize" contains lots of information relevant to
creating such functions f (given P1 and P2). Thus Canonize is an example of
the concept Operation.
Canonize also contains
information relevant to dealing with any and all such f's. So
Canonize is a specialization of Operation.
The final specialization of Operation is CONSTANT. This kind of operation
accepts an argument or two and then ignores it. It returns the same value, no
matter what is fed to it.
IDENTITY is just what it claims to be. It takes one argument and returns it
immediately. Neither Identity nor any Constant operation is very interesting (unless
some new concept turns out unexpectedly to be equivalent to one of them).
INSERT specifies a whole bunch of structural insertion operations. They each
take an element (anything) and a particular brand of structure, and produce a new
structure by adding the element to the given structure. The precise flavor varies
depending on the kind of structure involved. With Set-insert, e.g.,
the algorithm is complicated by the constraint that no multiple elements may
be present. With Bag-insert(x,B), however, the item x is simply dumped inside bag B.
DELETE is analogous. It tries to remove a given item from a given structure.
.ONCE TURN ON "{}"
JOIN-STRUCTURE is an operation which forms the union of two given structures.
The specializations of JOIN-STRUCTURE
include Set-union, Bag-union, Oset-union, and
List-union.
Each of these concepts is covered in detail in Appendix {[2] ALLCON}.
DIFFERENCE computes the structural difference between two given structures.
For sets, this is simply Set-difference (which we all know and love); for
Lists, there is no "obvious" definition, so some ⊗4ad hoc⊗* one was made.
The reader is pointed to the appendix of concepts, where that level of
detail will be made clear.
Another bunch of concepts exist for
intersecting a pair of structures, taking the
first element (for ordered structures) of a structure, the last element,
removing the first element$$ called "All-but-first-element". This transforms an
ordered structure into a new ordered structure. It is analogous to "CDR". $, etc.
REVERSE accepts an ordered structure and reverses it (at the top-level
only).
REPLACE(S,F) accepts a structure S and an operation F. It replaces each item
s⊗6ε⊗*S by a value of F(s). If S is (BAG 2 A (B)), and F is a constant function
which always returns "1", then the result of the Replacing would be
(BAG 1 1 1). If F were the operation Identity, then the bag would be unchanged.
REPEAT(S,E) accepts a structure S and a self-contained program E (any executable
expression). AM then evaluates E over and over, as many times as there are
elements in S. If E requires an argument, then this operation works like the
Interlisp function MAPC. It repeatedly draws an element x out of the structure S,
then runs E with x as its argument. This is done once for each member of S.
. SSSEC(Rationale behind Choice of Concepts)
The shortness of this section may be all you need to observe before
moving on to the next one.
Seriously, a necessary part of realizing AM was to choose a
particular set of starting concepts. But how should such a choice be
made?
My first impulse was to gather a ⊗4complete⊗* set of concepts. That
is, a basis which would be sufficient to derive all mathematics. The
longer I studied this, the larger the estimated size of this basis
grew. Even after just a few hours of thought, it became clear that
this would never fit in 256k. $$ This is the size of the core memory
of the computer I had at my disposal. $ One philosophical problem
here is that future mathematics may be inspired by some real-world
phenomena which haven't even been observed yet. Aliens visiting Earth
might have a different mathematics from ours, since their collective
life experiences would be quite different from we Terrans.
Scrapping the idea of a sufficient basis, what about a necessary one?
That is, a basis which would be ⊗4minimal⊗* in the following sense:
if you ever removed a concept from that basis, it could never be
re-discovered. In isolated cases, one can tell when a basis is
⊗4not⊗* minimal: if it contains both addition and multiplication,
then it is too rich, since the latter can be derived from the
former.$$ by AM, and by any mathematician. As Don Cohen points out,
if the researcher lacked the proper discovery methods, then he might
never derive Times from Plus. $ And yet, the same problem about
"absoluteness" cropped up: how can anyone claim that the discovery of
X can ⊗4never⊗* be made from a given starting point? Until recently,
mathematicians didn't realize how natural it was to derive numbers
and arithmetic from set theory (a task which AM does, by the way)$$
The "new math" is trying to get young children to do this as well;
unfortunately, no one showed the elementary-school teachers the
underlying harmony, and the results have been saddening. $. So 50
years ago the concepts of set theory and number theory would both
have been undisputedly placed into a "minimal" basis. There are thus
no absolute conceptual primitives; each culture (perhaps even each
individual) possesses its own basis.
Since I couldn't give AM a minimal basis, nor a complete one, I
decided AM might as well have a ⊗4nice⊗* one. Although it won't be
minimal, it should nevertheless be made very small (order of
magnitude: 100 concepts). Although it won't be complete, it should
suffice for re-discovering much of already-known mathematics.
Finally, it should be ⊗4rational⊗*, by which I mean that there should
be a simple rule for deciding which concepts do and don't belong in
that basis.
The concepts AM starts with are meant to be those possessed by young
children (age 4, say). This explains some omissions of concepts which
would otherwise be considered fundamental: (i) Proof and techniques
for proof/disproof; (ii) Abstract properties of relations, like
associativity, single-valued, onto; (iii) Cardinality, arithmetic;
(iv) Infinity, continuity, limits. The interested reader should see
[Piaget] or [Copeland].
Because my programming time and the PDP-10's memory space were both quite small,
only some of the "pre-numerical" concepts
could be included. Some unjustified omissions are: (i) visual
operations, like rotation, coloration; (ii) Games, rules, procedures,
strategies, tactics; (iii) Geometric notions, like outside, between.
AM is not supposed to be a model of a child, however.
It would be
repugnant (and much too hard for me) to try to emulate a human child's
whimsical imagination and emotive drives.
And AM is not ripe for "teaching", as are children.
$$ Learning psychologists might label AM as neo-behavioristic and cognitivistic. See
[LeFrancois]. $
A more faithful image is that of Ramanujan, a brilliant modern
mathematician who received a very poor education, and was forced to
re-derive much of known number theory all by himself.
.ONCE TURN ON "{}"
There is no formal justification for the particular set of starting
concepts. They are all reasonably primitive (sets, composition), and
lie several levels "below" the ones which AM managed to ultimately
derive (prime factorization, square-root). It might be valuable to
attempt a similar automated math discoverer, which began with a very
different set of concepts (e.g., start it out as an expert in lattice
theory, possessing all known concepts thereof). The converse kind of
experiments are to vary the initial base of concepts, and observe the
effects on AM's behavior. A few experiments of that form are
described in Section {[2]EXPT}.{[2]EXPTSSEC}.